﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"test.h"
//                                                        2023.3.29 strlen函数的优化实现
//int my_strlen(char const *arr)              
//{
//	assert(arr);
//	int i=0, count=0;
//	while (*(arr + i) != '\0')
//	{
//		i++;
//		count++;
//	}
//	return i;
//}
//int main()
//{
//	char arr[100];
//	gets(arr);
//	
//	printf("%d", my_strlen(arr));
//	return 0;
//}

//#include<stdio.h>                                        //实现strcpy函数优化函数；
//#include<assert.h>   
//
//char* my_strcpy(char* arr1,const char* arr2)
//{
//	char* arr3 = arr1;
//	assert(arr2);
//	assert(arr1);
//	while (*arr1++ = *arr2++);
//	return arr3;
//}
//int main()
//{
//	char arr1[1000], arr2[1000];              
//	gets(arr2);
//	printf("%s", my_strcpy(arr1, arr2));
//	return 0;
//}

//#include<stdio.h>
//#include<assert.h>						//将数组的奇数与偶数分离；
//
//int * separate(int* arr)//我的方法
//{
//	int i=0,j=0;
//	int arr1[1000];
//	while (*(arr + i) != '\0')
//	{
//		if ((*(arr + i)) % 2 != 0)
//		{
//			arr1[j] = *(arr + i);
//			j++;
//		}
//		i++;
//	}
//	i = 0;
//	while (*(arr + i) != '\0')
//	{
//		if (*(arr + i) % 2 == 0)
//		{
//			arr1[j] = *(arr + i);
//			j++;
//		}
//		i++;
//	}
//	arr1[j] = *(arr + i);
//	for (int j = 0; j <=i; j++)
//	{
//		*(arr + j) = arr1[j];
//	}
//	return arr;
//}
//void swap_arr(int arr[], int sz)//比特方法
//{
//	int left = 0;
//	int right = sz - 1;
//	int tmp = 0;
//
//
//	while (left < right)
//	{
//		// 从前往后，找到一个偶数，找到后停止
//		while ((left < right) && (arr[left] % 2 == 1))
//		{
//			left++;
//		}
//
//		// 从后往前找，找一个奇数，找到后停止
//		while ((left < right) && (arr[right] % 2 == 0))
//		{
//			right--;
//		}
//
//		// 如果偶数和奇数都找到，交换这两个数据的位置
//		// 然后继续找，直到两个指针相遇
//		if (left < right)
//		{
//			tmp = arr[left];
//			arr[left] = arr[right];
//			arr[right] = tmp;
//		}
//	}
//}
//int main()
//{
//	int arr[1000],n,i;
//	scanf("%d", &n);//输入元素个数；
//	for (i=0; i < n; i++)
//	{
//		scanf("%d", &arr[i]);//输入元素；
//	}
//	arr[i] = '\0';
//	swap_arr(arr, n);
//	//separate(arr);
//	for (i = 0; i < n; i++)
//	{
//		printf("%d",arr[i]);
//	}
//	return 0;
//}
//								//打印杨辉三角；
//#include<stdio.h>
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int arr[100][100]={0};
//	arr[0][1] = 1;
//	arr[1][1] = 1;
//	for (int i = 1; i <=n; i++)
//	{
//		for (int j = 1; j <=i; j++)
//		{
//			arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
//			printf("%d", arr[i][j]);
//		}
//		printf("\n");
//	}
//
//	return 0;
//}
										//猜凶手
//#include<stdio.h>
//int main()
//{
//	int a = 1, b = 2, c = 3, d = 4,killer=0;//给abcd四个人分配序号
//	for (int killer = 1; killer < 5; killer++)
//	{
//		while (((killer != 1) + (killer == 3) + (killer == 4) + (killer != 4)) == 3)
//		{
//			switch(killer)
//			{
//			case 1:
//				printf("杀手是a\n");
//				break;
//			case 2:
//				printf("杀手是b\n");
//				break;
//			case 3:
//				printf("杀手是c\n");
//				break;
//			case 4:
//				printf("杀手是d\n");
//				break;
//			}
//			break;
//		}
//	}
//	return 0;
//}
								 //猜测名次；
//#include<stdio.h>
//int judge(int a, int b, int c, int d, int e)
//{
//	if (a == b || a == c || a == d || a == e || b == c || b == e || b == d || c == d || c == e || e == d)
//		return 0;
//}
//int main()
//{
//	int a, b, c, d, e;
//	for (int a = 1; a <= 5; a++)
//	{
//		for (int b = 1; b <= 5; b++)
//		{
//			for (int c = 1; c <= 5; c++)
//			{
//				for (int d = 1; d <= 5; d++)
//				{
//					for (int e = 1; e <= 5; e++)
//					{
//						while ((((b == 2) + (a == 3)) == 1) &&
//							(((b == 2) + (e == 4)) == 1) &&
//							(((d == 2) + (c == 1)) == 1) &&
//							(((c == 5) + (d == 3)) == 1) &&
//							(((a == 1) + (e == 4)) == 1) && judge(a, b, c, d, e))
//						{
//							printf("a=%d,b=%d,c=%d,d=%d,e=%d", a, b, c, d, e);
//							break;
//						}
//					}
//				}
//			}
//		}
//	}
//	return 0;
//}
//                                  计算数据类型大小
//int main()
//{	
//	int a = 0;
//	printf("%d\n", sizeof(int));//       整形
//	printf("%d\n", sizeof(short));
//	printf("%d\n", sizeof(long long));
//	printf("%d\n", sizeof(char));
//
//	printf("%d\n", sizeof(double));//   浮点型
//	printf("%d\n", sizeof(float));
//	return 0;
//}
//                               整形在内存中是怎么存储的以及大小端存储
//int main()
//{
//	int a = 1;
//	char b = 0;
//	int d = -1;
//	char* c = (char*)&a;
//	return 0;
//}
//									求最大公约数；
//int main()
//{
//	int m, n,t=1;
//	scanf("%d%d", &m, &n);
//	while (t)
//	{
//		t = m % n;
//		m = n;
//		n = t;
//	}
//	printf("%d", m);
//	return 0;
//}
//									数九的个数；
//int main()
//{
//	int n,count=0;
//	for (int i = 1; i <= 100; i++)
//	{
//		n = i;
//		while (n)
//		{
//			if ((n % 10) == 9)
//			{
//				count++;
//			}
//			n /= 10;
//		}
//	}
//	printf("%d", count);
//	return 0;
//}
//                                   九九乘法表
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	for (int i = 1; i < n; i++)
//	{
//		for (int j = 1; j <=i; j++)
//		{
//			printf("%d*%d=%d ", i, j, i * j);
//		}
//		printf("\n");
//	}
//	return 0;
//}
//										猜数字游戏
//void game()
//{
//	int n=-1,answer;
//	answer = (rand() % 100 + 1);
//	printf("%d\n", answer);
//	while (answer!= n)
//	{
//		printf("请输入》:\n");
//		scanf("%d", &n);
//		system("cls");
//		if (n > answer)
//		{
//			printf("猜大了\n");
//		}
//		else if (n < answer)
//		{
//			printf("猜小了\n");
//		}
//	}
//	if (n == answer)
//		printf("恭喜你猜对了\n");
//}
//void menu()
//{
//	printf("******请输入》；********\n");
//	printf("******1:进入游戏********\n");
//	printf("******0:退出游戏********\n");
//	printf("************************\n");
//}
//int main()
//{
//	srand((unsigned int)time(NULL));
//	int n;
//	do
//	{
//		menu();
//		scanf("%d", &n);
//		switch (n)
//		{
//		case 1:
//			printf("进入游戏\n");
//			game();
//				break;
//		case 0:
//			printf("退出游戏\n");
//				break;
//		}
//	} while (n);
//	return 0;
//}
//													有序数列查找下标
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,8,9,10,11,12,13 };
//	int left = 0;
//	int right = sizeof(arr) / sizeof(arr[0])-1;
//	while (left < right)
//	{
//		int tem;
//		tem = arr[left];
//		arr[left] =arr [right];
//		arr[right] = tem;
//		left++;
//		right--;
//	}
//	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
//	{
//		printf("%d\n", arr[i]);
//	}
//	return 0;
//}
//                                   打印素数
//int main()
//{
//	for (int i = 100; i <= 200; i++)
//	{
//		int judge = 0;
//		for (int j = 2; j <sqrt(i)+1; j++)
//		{
//			if (i % j == 0)
//			{
//				judge = 1;
//				break;
//			}
//		}
//		if (judge == 0)
//		{
//			printf("%d是素数\n", i);
//		}
//	}
//	return 0;
//}
//										判断闰年
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	if (n % 4 == 0 && n % 100 != 0 || n % 400 == 0)
//	{
//		printf("%d是闰年", n);
//	}
//	else
//		printf("%d不是闰年",n);
//	return 0;
//}
//                                     递归打印整数的每一位
//void separate(int n)
//{
//	if (n)
//	{
//		printf("%d\n", n % 10);
//		separate(n / 10);
//	}
//}
//int main()
//{
//	int n;
//	scanf("%d",&n);
//	separate(n);
//	return 0;
//}
//                                    递归方式打印阶乘
//int fac(int n)
//{
//	if (n)
//	{
//		return n * fac(n - 1);
//	}
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	printf("%d",fac(n));
//	return 0;
//}
//											strlen的模拟用递归与非递归
//int my_strlen1(char* arr)//递归方式
//{
//	if ((*arr) != '\0')
//	{
//		return 1 + my_strlen1(arr + 1);
//	}
//}
//int my_strlen2(const char* arr)//非递归
//{
//	int count = 0;
//	while (*arr++)
//	{
//		count++;
//	}
//	return count;
//}
//int main()
//{
//	char arr[] = "123456789";
//	printf("%d\n", my_strlen1(arr));
//	printf("%d\n", my_strlen2(arr));
//	return 0;
//}
//										用递归将字符串逆置
//void reverse(char*arr)
//{
//	int count = my_strlen1(arr);
//	count -= 1;
//	if(*arr&&count)
//	{
//		char tem = *(arr);
//		*(arr) = *(arr + count);
//		*(arr + count) = '\0';
//		reverse(arr + 1);
//		*(arr + count) = tem;
//	}
//}
//int my_strlen1(char* arr)
//{
//	if ((*arr) != '\0')
//	{
//		return 1 + my_strlen1(arr + 1);
//	}
//}
//int main()
//{
//	char arr[]="abcdef";
//	reverse(arr);
//	printf("%s", arr);
//	return 0;
//}
//										递归计算每个数位之和
//int DigitSum(int n)
//{
//	int sum;
//	sum = n % 10;
//	if (n)
//	{
//		sum = sum + DigitSum(n / 10);
//		return sum;
//	}
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	printf("%d", DigitSum(n));
//	return 0;
//}
//									递归实现n的k次方
//int my_pow(int n,int k)
//{
//	if (k)
//	{
//		return(n * my_pow(n, k - 1));
//	}
//
//}
//int main()
//{
//	int n, k;
//	scanf("%d%d", &n, &k);
//	printf("%d\n",my_pow(n, k));
//	return 0;
//}
//									用递归与非递归表示斐波那契数2023.4.1起
//int digit1(int n)//递归
//{
//	if (n <= 1)
//	{
//		return n;
//	}
//	else
//	{
//		return digit1(n - 1) + digit1(n - 2);
//	}
//}
//int digit2(int n)
//{
//	int a = 1, b = 1, c = 1,i=3;
//	if (n <= 2)
//	{
//		return 1;
//	}
//	else if (n == 0)
//	{
//		return 0;
//	}
//	else
//	{
//		while (i<=n)
//		{
//			c = a + b;
//			a = b, b = c;
//			i++;
//		}
//		return b;
//	}
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	printf("%d\n", digit1(n));
//	printf("%d\n", digit2(n));
//}
//                               最大公约数；
//#include<stdio.h>
//int main()
//{
//    int a, b, c;
//    scanf("%d%d", &a, &b);
//    c = a % b;
//    if (c == 0)
//    {
//        printf("%d", b);
//    }
//    while (c)
//    {
//        a = b;
//        b = c;
//        c = a % b;
//    }
//    printf("%d", b);
//    return 0;
//}
////                               最小公倍数
//int main()//时间效率低的算法
//{
//	int a, b;
//	long long c;
//	scanf("%d%d", &a, &b);
//	c = b;
//	while (1)
//	{
//		if (c % a == 0 && c % b == 0)
//		{
//			break;
//		}
//		c++;
//	}
//	printf("%lld", c);
//	return 0;
//}                         
//int main()//高效算法
//{
//	long long a, b,i=1;
//	scanf("%lld%lld", &a, &b);
//	while (a * i % b != 0)
//	{
//		i++;
//	}
//	printf("%lld", a * i);
//	return 0;
//}
//                   考试题目
//int main()//我的算法
//{
//	char arr[101] ={'\0'};
//	int b = 0;
//	int locala[101]={0};//每个单词的首地址
//	int a = 1;
//	gets(arr);
//	int len=strlen(arr)-1;
//	for (int i = 2; i < len; i++)//找出每个单词的首地址
//	{
//		if (arr[i - 1] == ' ' && arr[i] != ' ')
//		{
//			locala[a] = i;
//			a++;
//		}
//	}
//	for (int i = a; i >0; i--)//从最后一个单词的首地址开始
//	{
//		int c = locala[i-1];
//		while(arr[c] != ' '&&arr[c]!='\0')
//		{
//			printf("%c", arr[c]);
//			c++;
//		}
//		if (i != 1)
//		{
//			printf(" ");
//		}
//	}
//	return 0;
//}
//void reserve(int left,int right,char arr[])//比特算法--先把字符串逆序再把单词逆序
//{
// 	while (left < right)
//	{
//		char tem = arr[left];
//		arr[left] = arr[right];
//		arr[right] = tem;
//		right--;
//		left++;
//	}
//}
//int main()
//{
//	char arr[101] = { 0 };
//	int i = 0,j=0;
//	gets(arr);
//	int right = strlen(arr) - 1, left = 0;
//	reserve(left ,right,arr);
//	while (arr[i] != '\0')
//	{
//		while (arr[i] != ' '&&arr[i]!='\0')
//		{
//			i++;
//		}
//		right = i - 1;
//		reserve(left, right, arr);
//		left = i + 1;
//		i++;
//	}
//	printf("%s", arr);
//	return 0;
//}
//                                        求最小公倍数——我的算法
//int main()
//{
//    long long a, b,d;
//    long long c;
//    scanf("%lld%lld", &a, &b);
//    d = a * b;
//    for (c = b; c <= a * b; c += b)
//    {
//        if (c % a == 0 && c % b == 0)
//        {
//            printf("%lld", c);
//            break;
//        }
//    }
//    return 0;
//}
//                                           对于指针数组的测试；2023.4.2始
//int main()
//{
//	int arr[] = { 1,2,3,4 };
//	int arr1[100]={0};
//	int* arr2[2] = { arr,arr1 };
//	printf("%d\n%d\n", *arr2[0],*arr2[1]);
//	printf("%d\n%d\n", sizeof(arr), sizeof(arr1));
//
//	return 0;
//}
//											冒泡排序
//int main()
//{
//	int arr[10] = {0};
//	int n;
//	for (int i = 0; i < 10; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	int count = 0;
//	while (arr[count] != '\0')
//	{
//		count++;
//	}
//	for (int i = 0; i < count - 1; i++)
//	{
//		int is_change=0;//优化
//		for (int j = 0; j < count - i - 1; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				int tem = arr[j];
//				arr[j] = arr[j + 1];
//				arr[j + 1] = tem;
//				is_change=1;
//			}
//		}
//		if(!is_change)//优化
//		{
//			break;
//		}
//	}
//	for (int i = 0; i < count; i++)
//	{
//		printf("%d", arr[i]);
//	}
//}
//											数组操作
//void init(int* arr,int sz)//初始化数组为0
//{
//	for (int i = 0; i < sz; i++)
//	{
//		arr[i] = 0;
//	}
//}
//void print(int* arr, int sz)//数组打印
//{
//	for (int i = 0; i < sz; i++)
//	{
//		printf("%d\n", *(arr + i));
//	}
//}
//void reverse(int* arr, int sz)//数组逆序
//{
//	int left = 0;
//	int right = sz - 1;
//	while (left < right)
//	{
//		int tem = arr[left];
//		arr[left] = arr[right];
//		arr[right] = tem;
//		left++;
//		right--;
//	}
//}
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	print(arr, sz);
//	reverse(arr, sz);
//	for (int i = 0; i < sz; i++)
//	{
//		printf("%d\n", arr[i]);
//	}
//	init(arr,sz);
//	for (int i = 0; i < sz; i++)
//	{
//		printf("%d\n", arr[i]);
//	}
//	return 0;
//}
//									数组内容交换
//void swap(char* arr1, char* arr2,int sz)
//{
//	for (int i = 0; i < sz; i++)
//	{
//		char tem = arr1[i];
//		arr1[i] = arr2[i];
//		arr2[i] = tem;
//	}
//}
//int main()
//{
//	char arr1[] = "123456789";
//	char arr2[] = "987654321";
//	int sz = strlen(arr1);
//	swap(arr1,arr2,sz);
//	printf("%s\n%s", arr1, arr2);
//	return 0;
//}
//									喝汽水问题
//int main()
//{
//	int bottle = 0,moeny=20,count=0,drink=0;
//	while (moeny)
//	{
//		drink=moeny;
//		count += drink;
//		bottle += drink;
//		moeny = bottle / 2;
//		bottle = bottle-moeny * 2;
//	}
//	printf("%d", count);
//	return 0;
//}
//											求二进制多少位不同位操作符多种解法2023.4.3起始
//int main()
//{
//	int m, n,count=0;
//	scanf("%d%d", &m, &n);
//	n = m ^ n;
//	while (n)
//	{
//		n = n & (n - 1);//每次消去最小位的1；
//		count++;
//	}
//	printf("%d", count);
//	return 0;
//}
//										打印二进制数的所以奇数位和偶数位
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	for (int i = 31; i >= 1; i -= 2)
//	{
//		printf("%d ", (1 & (n >> i)));
//	}
//	printf("\n");
//	for (int i = 30; i >= 0; i -= 2)
//	{
//		printf("%d ", (1 & (n >> i)));
//	}
//	return 0;
//}
//                                         写一个函数返回参数二进制中 1 的个数。
//int main()
//{
//	int n,count=0;
//	scanf("%d", &n);
//	while (n)
//	{
//		n = n & (n - 1);
//		count++;
//	}
//	printf("%d", count);
//	return 0;
//}
//											打印菱形
//int main()
//{
//	int n;//菱形的边长单位（*的个数）
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j <n-i-1; j++)
//		{
//			printf(" ");
//		}
//		for (int j = 0; j < i * 2 + 1; j++)
//		{
//			printf("*");
//		}
//		printf("\n");
//	}
//	for (int i = n-1; i >0; i--)
//	{
//		for (int j = 0; j <n-i; j++)
//		{
//			printf(" ");
//		}
//		for (int j = 0; j <i*2-1; j++)
//		{
//			printf("*");
//		}
//		printf("\n");
//	}
//	return 0;
//}
//			                            多组数据算平均值；					
//int main() {
//    int n;
//    int max = 0, min = 100, m = 0, sum = 0;
//    while ((scanf("%d", &n)) != EOF)
//    {
//        if (n > max)
//        {
//            max = n;
//        }
//        if (n < min)
//        {
//            min = n;
//        }
//        m++;
//        sum += n;
//        if (m == 7)
//        {
//            printf("%.2f", (sum - min - max) / 5.0);
//            max = 0, min = 100, m = 0, sum = 0;
//        }
//    }
//    return 0;
//}
//										杨氏矩阵找数字；
//int find(int arr[][10],int n)
//{
//	int x = 10, y = 10, i=0, j=y-1;
//	while (i < x && j >= 0)
//	{
//		if (arr[i][j] == n)
//		{
//			return 1;
//			break;
//		}
//		else if (arr[i][j] < n)
//		{
//			i++;
//		}
//		else
//		{
//			j--;
//		}
//	}
//	return 0;
//}
//int main()
//{
//	int n,arr[10][10];
//	scanf("%d", &n);
//	for (int i = 0; i < 10; i++)
//	{
//		arr[i][0] = 1 + i;
//		for (int j = 1; j < 10; j++)
//		{
//			arr[i][j] = arr[i][j - 1] + 1;
//		}
//	}
//	if (find(arr, n) == 1)
//	{
//		printf("找到了！\n");
//	}
//	else
//	{
//		printf("没找到！\n");
//	}
//	system("pause");
//	return 0;
//}
//												左旋字符
//int main()
//{
//	char arr[] = "abcdefg";
//	int n,last= strlen(arr);
//	scanf("%d", &n);
//	n = n % (last);
//	for (int i = 0; i < n; i++)
//	{
//		char tem = arr[0];
//		for (int j = 1; j < last; j++)
//		{
//			arr[j - 1] = arr[j];
//		}
//		arr[last - 1] = tem;
//	}
//	printf("%s", arr);
//	system("pause");
//	return 0;
//}
//													qsort函数的实现
//int cmp(const void* e1, const void* e2)
//{
//	return (*(int*) e1 - *(int*)e2);
//}
//void bubble_sort(void* base, int num, int width, int (*cmp)(const void* e1, const void* e2))
//{
//	int i, j;
//	for (i = 0; i < num-1; i++)
//	{
//		for (j = 0; j < num - 1 - i; j++)
//		{
//			if (cmp((char*)base + width * j, (char*)base + (j + 1) * width) > 0)
//			{
//				char* p1 = (char*)base + width * j;
//				char* p2 = (char*)base + (j + 1) * width;
//				for (int k = 0; k < width; k++)
//				{
//					char tem = *p1;
//					*p1 = *p2;
//					*p2 = tem;
//					p1++;
//					p2++;
//				}
//			}
//		}
//	}
//}
//void test1()
//{
//	int arr[] = { 1,5,8,7,9,4,6,3,2,0 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	bubble_sort(arr,sz,sizeof(arr[0]),cmp);
//	for (int i = 0; i < sz; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//}
//int main()
//{
//	test1();
//	return 0;
//}
//												对qsort函数的练习
//struct stu
//{
//	char name[20];
//	char number[20];
//	double score;
//}arr[]={{"zhangsan","2255010",90.5},{"lisi","22550101",80.5},{"wangwu","22550102",85.5}};
//int cmp_score(const void*e1,const void *e2)
//{
//	return (((struct stu*)e2)->score - ((struct stu*)e1)->score);
//}
//int cmp_int(const void* e1, const void* e2)
//{
//	return(*(int*)e1 - *(int*)e2);
//}
//int main()
//{
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	qsort(arr, sz, sizeof(arr[0]), cmp_score);
//	int arr1[] = { 1,2,5,89,6,26,1,5,6,8,4,5,35,8,9,75 };
//	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
//	qsort(arr1, sz1, sizeof(arr1[0]), cmp_int);
//	for (int i = 0; i < sz1; i++)
//	{
//		printf("%d ", arr1[i]);
//	}
//	return 0;
//}
//												判断是否为旋转字符串
//int is_(char s1[],char s[])
//{
//	int sz = strlen(s1);
//	for (int i = 0; i <=sz; i++)
//	{
//		char tem = s1[0];
//		for (int j = 1; j < sz; j++)
//		{
//			s1[j - 1] = s1[j];
//		}
//		s1[sz-1] = tem;
//		if (strcmp(s1, s) == 0)
//		{
//			printf("相同\n");
//			return 1;
//		}
//	}
//	printf("不是的\n");
//	return 0;
//}
//int main()
//{
//	char s1[] = "aabbccdd", s2[] = "abcdef";
//	char s[1000];
//	gets(s);
//	is_(s1,s);
//	return 0;
//}
//													模拟实现strstr函数
//char* my_strstr(const char*arr,const char* arr1)
//{
//	assert(arr && arr1);
//	const char* str = arr;
//	const char* str1 = arr1;
//	const char* cur = arr;
//	while (*cur)
//	{
//		str = cur;
//		str1 = arr1;
//		while ((*str1 == *str) && *str && *str1)
//		{
//			str++;
//			str1++;
//		}
//		if (*str1=='\0')
//		{
//			return (char*)cur;
//		}
//		cur++;
//	}
//	return NULL;
//}
//int main()
//{
//	char arr[] = "abcdefgh";
//	char arr1[] = "cde";
//	char* ret = my_strstr(arr, arr1);
//	if (ret == NULL)
//	{
//		printf("没有找到\n");
//	}
//	else
//		printf("%s\n",ret);
//	return 0;
//}
//												模拟实现strcat函数
//char* my_strcat(char*arr1, const char*arr2)
//{
//	char* ret = arr1;
//	assert(arr1 && arr2);
//	while (*arr1 != '\0')
//	{
//		arr1++;
//	}
//	while (*arr1++ = *arr2++);
//	return ret;
//}
//int main()
//{
//	char arr1[20] = "good ";
//	char arr2[] = "morning";
//	char*ret= my_strcat(arr1, arr2);
//	printf("%s", ret);
//	return 0;
//}
//												模拟实现strcmp函数
//int my_strcmp(const char*arr1,const char*arr2)
//{
//	assert(arr1 && arr2);
//	while (*arr1 == *arr2&&*arr1&&*arr2)
//	{
//		arr1++;
//		arr2++;
//	}
//	if ((*arr1 - *arr2) > 0)
//	{
//		return 1;
//	}
//	else if ((*arr1 - *arr2) < 0)
//	{
//		return -1;
//	}
//	else
//	{
//		return 0;
//	}
//}
//int main()
//{
//	char arr1[] = "abcde";
//	char arr2[] = "abcde";
//	char arr3[] = "abcdf";
//	char arr4[] = "abcdafasd";
//	printf("%d\n", my_strcmp(arr1, arr2));
//	printf("%d\n", my_strcmp(arr1, arr3));
//	printf("%d\n", my_strcmp(arr1, arr4));
//	return 0;
//}
//													模拟实现strcpy
//char* my_strcpy(char* s1, const char* s2)
//{
//	assert(s1 && s2);
//	char* str = s1;
//	while (*s1++ = *s2++);
//	return str;
//}
//int main()
//{
//	char arr1[] = "abcdef";
//	char arr2[20] = {0};
//	printf("%s\n", my_strcpy(arr2, arr1));
//	return 0;
//}
//														模拟实现strlen函数
//int my_strlen1(const char* arr)//加法器
//{
//	int count = 0;
// 	while (*arr++)
//	{
//		count++;
//	}
//	return count;
//}
//int my_strlen2(const char* arr)//递归
//{
//	if (*arr)
//	{
//		return 1 + my_strlen2(arr + 1);
//	}
//}
//int my_strlen3(const char* arr)//指针
//{
//	char* arr1 = arr;
//	while (*arr1++)
//	{
//		;
//	}
//	return arr1 - arr-1;
//}
//int main()
//{
//	char arr[] = "123";
//	printf("%d\n", my_strlen1(arr));
//	printf("%d\n", my_strlen2(arr));
//	printf("%d\n", my_strlen3(arr));
//	return 0;
//}
//																memmove的实现
//void* my_memmove(void* arr1, const void* arr2, int count)
//{
//	assert(arr1&&arr2);
//	char* s1 = (char*)arr1;
//	char* s2 = (char*)arr2;
//	if (s1 < s2)
//	{
//		while (count)
//		{
//			*s1++ = *s2++;
//			count--;
//		}
//	}
//	else
//	{
//		while (count--)
//		{
//			*(s1 + count) = *(s2 + count);
//		}
//	}
//	return (void*)arr1;
//}
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int arr1[] = { 1,2,3,4,5,6,7,8,9,10 };
//	my_memmove(arr, arr + 2, 20);
//	my_memmove(arr1+2, arr1, 20);
//	for (int i = 0; i < 10; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	printf("\n");
//	for (int i = 0; i < 10; i++)
//	{
//		printf("%d ", arr1[i]);
//	}
//	return 0;
//}
//											memcpy函数实现
//void* my_memcpy(void* arr1, const void* arr2,int count)
//{
//	assert(arr1 && arr2);
//	char* s1 = (char*)arr1;
//	char* s2 = (char*)arr2;
//	while (count)
//	{
//		*s1 = *s2;
//		s1++;
//		s2++;
//		count--;
//	}
//	return (void*)arr1;
//}
//int main()
//{
//	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
//	int arr1[20] = { 0 };
//	my_memcpy(arr+2, arr,20);
//	return 0;
//}
//												再次练习strstr函数
//char* my_strstr(const char* arr1, const char* arr2)
//{
//	char* s1 = arr1;
//	char* s2 = arr2;
//	char* cur = arr1;
//	while (*cur)
//	{
//		s1 = cur;
//		s2 = arr2;
//		while (*s1 == *s2 && *s1 && *s2)
//		{
//			s1++;
//			s2++;
//		}
//		if (!*s2)
//		{
//			return cur;
//		}
//		if (!*s1)
//		{
//			return NULL;
//		}
//		cur++;
//	}
//	return NULL;
//}
//int main()
//{
//	char arr1[] = "abccdefg";
//	char arr2[] = "cdef";
//	char arr3[] = "de";
//	char*ptr=my_strstr(arr1,arr2);
//	char* ptr1 = my_strstr(arr1, arr3);
//	if (ptr == NULL)
//	{
//		printf("没找到\n");
//	}
//	else
//	{
//		printf("%s\n", ptr);
//	}
//	if (ptr1 == NULL)
//	{
//		printf("没找到\n");
//	}
//	else
//	{
//		printf("%s\n", ptr1);
//	}
//	return 0;
//}
//													练习strcat函数
//char* my_strcat(char* arr1, const char* arr2)
//{
//	assert(arr1 && arr2);
//	char* str = arr1;
//	while (*arr1)
//	{
//		arr1++;
//	}
//	while (*arr1++ = *arr2++)
//	{
//		;
//	}
//	return str;
//}
//int main()
//{
//	char arr1[] = "i love \0xxxxxxxx";
//	char arr2[] = "you\0aaaaaa";//我通过这里的赋值清楚的看到了while（）中的指令不满足后会执行完（）中条件再 跳出；
//	my_strcat(arr1,arr2);
//	return 0;
//}
//													memset函数
//int main()
//{
//	int arr[10] = { 1,2,3,4,5,6,7,8,9 ,10 };
//	memset(arr, 0, 20);
//	for (int i = 0; i < 10; i++)
//	{
//		printf("%d  ", arr[i]);
//	}
//	return 0;
//}
//												strtok函数
//int main()
//{
//	char arr[] = "5201314@qq.com";
//	char arr1[20] = { 0 };
//	strcpy(arr1, arr);//临时拷贝
//	char* str2 = "@.";
//	char* str1 = strtok(arr1, str2);
//	while (str1!=NULL)
//	{
//		printf("%s\n", str1);
//		str1 = strtok(NULL, str2);
//	}
//	return 0;
//}
//												memcpy函数
//void* my_memcpy(void*str1,const void*str2,int count)
//{
	//char* s1 = (char*)str1;
	//char* s2 = (char*)str2;
	//while (count)
	//{
	//	*s1 = *s2;
	//	s1++;
	//	s2++;
	//	count--;
	//}
//	return (void*)str1;
//}
//int main()
//{
//	int arr1[] = { 1,2,0,3,4,5,6,7,8,9 };
//	int arr2[20] = { 0 };
//	char *p = "abc\0abc";
//	my_memcpy(arr2, arr1, 20);
//	my_memcpy(arr1+2, arr1,20);
//	for (int i = 0; i < 5; i++)
//	{
//		printf("%d ", arr2[i]);
//	}
//	printf("\n");
//	for (int i = 0; i < 10; i++)
//	{
//		printf("%d ", arr1[i]);
//	}
//	printf("\n");
//	return 0;
//}
//													memove函数
//void* my_memove(void* str1, const void* str2, int count)
//{
//	char* s1 = (char*)str1;
//	char* s2 = (char*)str2;
//	while (count--)
//	{
//		if (s1 > s2)
//		{
//			*(s1 + count) = *(s2 + count);
//		}
//		else
//		{
//			*s1++ = *s2++;
//		}
//	}
//	return (void*)str1;
//}
//int main()
//{
//	int arr1[] = { 1,2,3,4,5,6,7,8,9 };
//	int arr2[20] = { 0 };
//	my_memove(arr2,arr1,20);
//	my_memove(arr1, arr1 + 2, 20);
//	my_memove(arr1 + 2, arr1, 20);
//	return 0;
//}
//														memcmp函数练习
//int my_memcmp(const void* arr1, const void* arr2, int count)
//{
//	char* s1 = (char*)arr1;
//	char* s2 = (char*)arr2;
//	int num = 0;
//	while (count--)
//	{
//		if (*s1 > *s2)
//		{
//			return *s1 - *s2;
//		}
//		else if (*s1 < *s2)
//		{
//			return * s1 - *s2;
//		}
//		s1++;
//		s2++;
//	}
//	return 0;
//}
//int main()
//{
//	int arr1[] = { 1,2,3,4,5,6 };
//	int arr2[] = { 1,2,3,4,5,6 };
//	int arr3[] = { 1,2,3,4,4,6 };
//	int arr4[] = { 1,2,3,4,6,6 };
//	printf("%d\n", my_memcmp(arr1, arr2, 20));
//	printf("%d\n", my_memcmp(arr1, arr3, 20));
//	printf("%d\n", my_memcmp(arr1, arr4, 20));
//	return 0;
//}
//                                      变种水仙花
//int main() {
//    int a1, a2, a3, a4, a5, a6, a7, a8;
//    for (int a = 10000; a < 100000; a++) {
//        a1 = a / 10000;
//        a2 = a - a1 * 10000;
//        a3 = a / 1000;
//        a4 = a - a3 * 1000;
//        a5 = a / 100;
//        a6 = a - a5 * 100;
//        a7 = a / 10;
//        a8 = a - a7 * 10;
//        if (a == a1 * a2 + a3 * a4 + a5 * a6 + a7 * a8) {
//            printf("%d ", a);
//        }
//    }
//    return 0;
//}
//													判断字符
//int main() {
//    char n;
//    scanf("%c", &n);
//    if (n >= 'A' && n <= "Z" || n >= 'a' && n <= 'z')
//    {
//        printf("YES");
//    }
//    else {
//        printf("NO");
//    }
//    return 0;
//}
//														模拟实现strncat函数
//char* my_strncat(char* arr1, const char* arr2,int count)
//{
//	assert(arr1 && arr2);
//	int i;
//	char* s1 = arr1;
//	while (*s1)
//	{
//		s1++;
//	}
//	for (i = 0; i < count; i++)
//	{
//		*s1 = *arr2;
//		s1++;
//		if (!*arr2)
//		{
//			return arr1;
//		}
//		arr2++;
//	}
//	*s1 = '\0';
//	return arr1;
//}
//int main()
//{
//	char arr[50] = "hello \0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
//	char arr1[20] = "pretty girl!";
//	my_strncat(arr,arr1,10);
//	printf("%s", arr);
//	return 0;
//}
//														模拟实现strncpy
//char* my_strncpy1(char* arr1, const char* arr2, int count)//优化前
//{
//	char* s1 = arr1;
//	char* s2 = arr2;
//	int sum = 0;
//	while (*s2)
//	{
//		s2++;
//		sum++;
//	}
//	if (sum >= count)
//	{
//		for (int i = 0; i < count; i++)
//		{
//			*s1 = *arr2;
//			s1++;
//			arr2++;
//		}
//	}
//	else
//	{
//		for (int i = 0; i < sum; i++)
//		{
//			*s1 = *arr2;
//			s1++;
//			arr2++;
//		}
//		for (int i = sum; i < count; i++)
//		{
//			*s1 = '0';
//			s1++;
//		}
//	}
//	*s1 = '\0';
//	return arr1;
//}
//char* my_strncpy2(char* arr1, const char* arr2, int count)//优化后
//{
//	char* s1 = arr1;
//	char* s2 = arr2;
//	int sum = 0;
//	while (*s2)
//	{
//		s2++;
//		sum++;
//	}
//	for (int i = 0; i < count; i++)
//	{
//		if (i < sum)
//		{
//			*s1 = *arr2;
//			s1++;
//			arr2++;
//		}
//		else
//		{
//			*s1 = '0';
//			s1++;
//		}
//	}
//	*s1 = '\0';
//	return arr1;
//}
//int main()
//{
//	char arr[50] = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
//	char arr1[] = "abcdefgddddsffd";
//	my_strncpy1(arr,arr1,20);
//	printf("%s", arr);
//	return 0;
//}
//															对文件操作的练习
//int main()
//{
//	//打开文件
//	FILE* pa;
//	pa=fopen("data.txt", "r");
//	if (pa == NULL)
//	{
//		perror("fopen");
//		return;
//	}
//	//操作文件
//	//char s[] = "abcdef";//从标准输入流（键盘）中读入并写入文件；
//	//char max[1000];
//	//while (fgets(max, sizeof(max), stdin))
//	//{
//	//	fputs(max, pa);
//	//}
//	char max[1000];//从文件中读入并显示
//	while (fgets(max, sizeof(max), pa))
//	{
//		printf("%s", max);
//	}
//	//关闭文件
//	fclose(pa);
//	pa = NULL;
//	return 0;
//}
//												把菱形保存到文件中
//int main()
//{
//	FILE* pa = fopen("data.txt", "w");
//	if (pa == NULL)
//	{
//		printf("error\n");
//		return;
//	}
//	int n;//菱形的边长单位（*的个数）
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			fputc(' ', pa);
//		}
//		for (int j = 0; j < i * 2 + 1; j++)
//		{
//			fputc('*', pa);
//		}
//		fputc('\n', pa);
//	}
//	for (int i = n - 1; i > 0; i--)
//	{
//		for (int j = 0; j < n - i; j++)
//		{
//			fputc(' ', pa);
//		}
//		for (int j = 0; j < i * 2 - 1; j++)
//		{
//			fputc('*', pa);
//		}
//		fputc('\n', pa);
//	}
//	fclose(pa);
//	pa = NULL;
//	return 0;
//}
//													atoi函数实现
//int my_atoi(const char* str)
//{
//	assert(str);
//	int sum = 0,sign=1;
//	while(*str == ' ')
//	{
//		str++;
//	}
//	if (*str == '-')
//	{
//		sign = -1;
//		str++;
//	}
//	if (*str == '+')
//	{
//		str++;
//	}
//	if (*str < '0' && *str>'9')
//	{
//		return 0;
//	}
//	while (*str >= '0' && *str <= '9')
//	{
//		if (sum > INT_MAX / 10 || sum == INT_MAX / 10 && *str > 7)
//		{
//			if (sign == '-1')
//			{
//				return INT_MIN;
//			}
//			else
//			{
//				return INT_MAX;
//			}
//		}
//		sum = sum * 10 + (*str - '0');
//		str++;
//	}
//	return sign * sum;
//}
//int main()
//{
//	char str[] = "  12454j54gfh56789QWs";
//	printf("%d", my_atoi(str));
//	return 0;
//}
//												使用宏将二进制数奇偶位进行转化
//#define CHANGE_(n) (((n)&(0xaaaaaaaa))>>1|(((n)&(0x55555555))<<1))
//int main()
//{
//	int n;
//	scanf("%x", &n);
//	for (int i = 0; i < 32; i++)
//	{
//		printf("%d", ((n >> i) & 1));
//	}
//	printf("\n");
//	n = CHANGE_(n);
//	for (int i = 0; i < 32; i++)
//	{
//		printf("%d", ((n >> i) & 1));
//	}
//	return 0;
//}
//												offsetof宏的练习
//struct student {
//	char name[20];
//	int age;
//	float score;
//};
//int main()
//{
//	int sz = offsetof(struct student, age);
//	printf("%d", sz);
//	return 0;
//}
//												offsetof宏的实现
//#define OFFSIZEOF_(type,member) ((int)&((type*)0)->member)
//struct student {
//	char name[20];
//	int age;
//	float score;
//};
//int main()
//{
//	int sz = OFFSIZEOF_(struct student, age);
//	printf("%d", sz);
//	return 0;
//}
//#include<stdio.h>
//int main()
//{
//    int n, i = 0,sum=0,k=0;
//    int num[20] = { 0 };
//    char str[30] = { 0 };
//    scanf("%d", &n);
//    int tem = n;
//    while (tem)
//    {
//        num[i] = tem % 10;
//        tem /= 10;
//        i++;
//    }
//    for (int j=0; j<i; j++)
//    {
//        str[k] = num[j]+'0';
//        k++;
//        sum++;
//        if (sum % 3 == 0 && sum != i)
//        {
//            str[k] = ',';
//            k++;
//        }
//    }
//    for (int i = k - 1; i >= 0; i--)
//    {
//        printf("%c", str[i]);
//    }
//    return 0;
//}
//#include<stdio.h>
//#include<stdlib.h>
//int main()
//{
//	char s1[101] = { 0 };
//	char s2[101] = { 0 };
//	char s3[101] = { 0 };
//	int i = 0, j = 0;
//	gets(s1);
//	gets(s2);
//	char* a = s1;
//	while(*a)
//	{ 
//		char* b = s2;
//		int k = 0;
//		while (*b)
//		{
//			if (*a == *b)
//			{
//				k = 1;
//				break;
//			}
//			b++;
//		}
//		if (k == 0)
//		{
//			s3[i] = *a;
//			i++;
//		}
//		a++;
//	}
//	printf("%s", s3);
//	return 0;
//}
//												找最快步骤斐波那契数
//int main() {
//    int n, a = 0, b = 1, c = 1;
//    scanf("%d", &n);
//    int i = 0;
//    while (c < n)
//    {
//        c = a + b;
//        a = b;
//        b = c;
//    }
//    int min = n - a;
//    if (min > b - n)
//    {
//        min = b - n;
//    }
//    printf("%d", min);
//}
//											牛客网上题目置换空格字符
//class Solution {
//public:
//	void replaceSpace(char* str, int length) {
//		int sum = 0, len = 0;
//		char* s1 = str;
//		while (*s1)
//		{
//			if (*s1 == ' ')
//			{
//				sum++;
//			}
//			s1++;
//			len++;
//		}
//		int l = len - 1;
//		int n = len + sum * 2 - 1;
//		*(str + n + 1) = '\0';
//		while (n != l)
//		{
//			if (*(str + l) != ' ')
//			{
//				*(str + n) = *(str + l);
//				n--;
//				l--;
//			}
//			else
//			{
//				*(str + n) = '0';
//				n--;
//				*(str + n) = '2';
//				n--;
//				*(str + n) = '%';
//				n--;
//				l--;
//			}
//		}
//	}
//};
//												在从0到n的数字中查找少的数（时间复杂度为O（n））
//int missingNumber(int* nums, int n) {
//    int i = 0, num = 0;
//    int nums1[n + 1];
//    for (int j = 0; j < n + 1; j++)
//    {
//        nums1[j] = j;
//    }
//    for (i = 0; i < n; i++)
//    {
//        num ^= nums[i];
//    }
//    for (i = 0; i < n + 1; i++)
//    {
//        num ^= nums1[i];
//    }
//
//    return num;
//}
//												一组数字中数字都出现了两次，请写程序找出这两个只出现一次的数字
//int* singleNumbers(int* nums, int numsSize, int* returnSize) {
//
//    int i = 0, j = 0, ret = 0;
//    int single1 = 0;
//    int single2 = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        ret ^= nums[i];
//    }
//    for (i = 0; i < 32; i++)
//    {
//        if (((ret >> i) & 1) == 1)
//        {
//            break;
//        }
//    }
//    for (j = 0; j < numsSize; j++)
//    {
//        if (((nums[j] >> i) & 1) == 0)
//        {
//            single1 ^= nums[j];
//        }
//    }
//    single2 = ret ^ single1;
//    *returnSize = 2;
//    int* arr;
//    arr = (int*)malloc(8);
//    arr[0] = single1;
//    arr[1] = single2;
//    return arr;
//}
////														对顺序表的增删查改
//typedef int SLDateType;
//typedef struct SeqList
//{
//	SLDateType* a;
//	int size;
//	int capacity;
//}SeqList;
//
////对顺序表的检查
//void CheckSeqList(SeqList* ps)
//{
//	if (ps->capacity == ps->size)
//	{
//		SLDateType* tem = (SLDateType*)realloc(ps->a, sizeof(SLDateType*) * (ps->capacity += 4));
//		if (tem == NULL)
//		{
//			printf("检查出错误::1937\n");
//			exit(-1);
//		}
//		else
//		{
//			ps->a = tem;
//			printf("增容成功\n");
//			return;
//		}
//	}
//}
//// 对数据的管理:增删查改 
//void SeqListInit(SeqList* ps)//初始化顺序表
//{
//	ps->capacity = 4;
//	ps->size = 0;
//	ps->a=(SLDateType*)malloc(sizeof(SLDateType*) * 4);
//	if (ps->a == NULL)
//	{
//		printf("开辟空间失败\n：：1937");
//		exit(-1);
//	}
//}
//
//void SeqListDestroy(SeqList* ps)//顺序表的摧毁
//{
//	if (ps->a != NULL)
//	{
//		free(ps->a);
//		ps->a = NULL;
//	}
//}
//
//void SeqListPrint(SeqList* ps)//顺序表的打印
//{
//	assert(ps);
//	int i = 0;
//	for (i = 0; i < ps->size; i++)
//	{
//		printf("%d ", *((ps->a) + i));
//	}
//	printf("\n");
//}
//void SeqListPushFront(SeqList* ps, SLDateType x)//头插法
//{
//	assert(ps);
//	CheckSeqList(ps);//检查是否需要增容
//	for (int i = ps->size; i >0; i--)
//	{
//		ps->a[i] = ps->a[i - 1];
//	}
//	ps->a[0] = x;
//	ps->size++;
//}
//
//void SeqListPushBack(SeqList* ps, SLDateType x)//尾插法
//{
//	assert(ps);
//	CheckSeqList(ps);//检查是否需要增容
//	ps->a[ps->size] = x;
//	ps->size++;
//}
//
//void SeqListPopFront(SeqList* ps)//头删法
//{
//	assert(ps);
//	if (ps->size == 0)
//	{
//		printf("顺序表为空，无法删除\n");
//		return ;
//	}
//	else
//	{
//		int i = 1;
//		while (i < ps->size)
//		{
//			ps->a[i - 1] = ps->a[i];
//			i++;
//		}
//		ps->size--;
//	}
//}
//
//void SeqListPopBack(SeqList* ps)//尾删法
//{
//	assert(ps);
//	if (ps->size == 0)
//	{
//		printf("顺序表为空，无法删除\n");
//		return;
//	}
//	else
//	{
//		ps->size--;
//	}
//}
// //顺序表查找
//int SeqListFind(SeqList* ps, SLDateType x)
//{
//	assert(ps);
//	int i = 1;
//	while (i < ps->size)
//	{
//		if (ps->a[i - 1] == x)
//		{
//			return i - 1;
//		}
//		i++;
//	}
//	printf("没有找到这个数\n");
//	return -1;
//}
// //顺序表在pos位置插入x
//void SeqListInsert(SeqList* ps, int pos, SLDateType x)
//{
//	assert(ps);
//	assert(pos >= 0 && pos <= ps->size);
//	CheckSeqList(ps);//检查是否需要增容
//	int tem = ps->size-1;
//	while (pos<=tem)
//	{
//		ps->a[tem + 1] = ps->a[tem];
//		tem--;
//	}
//	ps->a[pos] = x;
//	ps->size++;
//}
// //顺序表删除pos位置的值
//void SeqListErase(SeqList* ps, int pos)
//{
//	assert(ps);
//	assert(pos >= 0 && pos < ps->size);
//	CheckSeqList(ps);//检查是否需要增容
//	while (pos < ps->size-1)
//	{
//		ps->a[pos] = ps->a[pos+1];
//		pos++;
//	}
//	ps->size--;
//}
//
//int main()
//{
//	int x;
//	SeqList s1;
//	SeqListInit(&s1);
//	for (int i = 0; i < 11; i++)
//	{
//		scanf("%d", &x);
//		SeqListPushBack(&s1, x);
//	}
//	SeqListPrint(&s1);
//	SeqListPopBack(&s1);
//	SeqListPopFront(&s1);
//	SeqListPrint(&s1);
//	SeqListPopBack(&s1);
//	SeqListPopFront(&s1);
//	SeqListPrint(&s1);
//
//	printf("%d\n", SeqListFind(&s1, 5));
//
//	SeqListInsert(&s1, 0, 1000);
//	SeqListPrint(&s1);
//
//	scanf("%d", &x);
//	SeqListErase(&s1, x);
//	SeqListPrint(&s1);
//
//	SeqListDestroy(&s1);
//	return 0;
//}
//													力扣原地移除数字题目
//int removeElement(int* nums, int numsSize, int val) {
//    int cur = 0, dst = 0;
//    while (cur < numsSize)
//    {
//        if (nums[cur] != val)
//        {
//            nums[dst] = nums[cur];
//            dst++;
//            cur++;
//        }
//        else
//        {
//            cur++;
//        }
//    }
//    return dst;
//}
//														删除有序数组中的重复项
//int removeDuplicates(int* nums, int numsSize) {
//    int cur = 1, dst = 0;
//    while (cur < numsSize)
//    {
//        if (nums[cur] == nums[dst])
//        {
//            cur++;
//        }
//        else
//        {
//            dst++;
//            nums[dst] = nums[cur];
//            cur++;
//        }
//    }
//    return dst + 1;
//}
//															合并两个有序数组
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {//普通算法
//    int j = 0;
//    for (int i = m; i < m + n; i++)
//    {
//        nums1[i] = nums2[j];
//        j++;
//    }
//    for (j = 0; j < m + n - 1; j++)
//    {
//        for (int i = 0; i < m + n - 1 - j; i++)
//        {
//            if (nums1[i] > nums1[i + 1])
//            {
//                int tem = nums1[i];
//                nums1[i] = nums1[i + 1];
//                nums1[i + 1] = tem;
//            }
//        }
//    }
//}
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {//省空间与时间的算法
//int p1 = m - 1, p2 = n - 1;
//int tail = m + n - 1;
//int cur;
//while (tail >= 0) {
//    if (p1 == -1)
//    {
//        nums1[tail] = nums2[p2];
//        p2--;
//    }
//    else if (p2 == -1)
//    {
//        nums1[tail] = nums1[p1];
//        p1--;
//    }
//    else if (nums1[p1] > nums2[p2])
//    {
//        nums1[tail] = nums1[p1];
//        p1--;
//    }
//    else
//    {
//        nums1[tail] = nums2[p2];
//        p2--;
//    }
//    tail--;
//}
//}
//														轮转数组
//void rotate(int* nums, int n, int k) {//空间换时间
//    int arr[n], num = 0;
//    k %= n;
//    for (int i = n - k; i < n; i++)
//    {
//        arr[num] = nums[i];
//        num++;
//    }
//    for (int i = 0; i < n - k; i++)
//    {
//        arr[num] = nums[i];
//        num++;
//    }
//    for (int i = 0; i < n; i++)
//    {
//        nums[i] = arr[i];
//    }
//}
//void swap(int* s, int left, int right)//O(1)算法，省时间也省空间
//{
//    while (left < right)
//    {
//        int tem = s[left];
//        s[left] = s[right];
//        s[right] = tem;
//        left++;
//        right--;
//    }
//}
//
//void rotate(int* nums, int n, int k) {
//    k %= n;
//    swap(nums, 0, n - k - 1);
//    swap(nums, n - k, n - 1);
//    swap(nums, 0, n - 1);
//
//}
//                                                                数组形式的整数加法
//#include<math.h>
//void swap(int* arr, int left, int right)
//{
//    while (left < right)
//    {
//        int tem = arr[left];
//        arr[left] = arr[right];
//        arr[right] = tem;
//        right--;
//        left++;
//    }
//}
//int* addToArrayForm(int* num, int numSize, int k, int* returnSize) {
//    int len = numSize > 4 ? numSize + 1 : 5;
//    int* arr = (int*)malloc((len) * 4);
//    int tem = k, sum = 0, i = 0;
//    int n = numSize - 1;
//    while (n >= 0)
//    {
//        int digit = tem % 10;
//        tem /= 10;
//        sum = num[n] + digit;
//        if (sum >= 10)
//        {
//            tem++;
//            sum -= 10;
//        }
//        arr[i] = sum;
//        i++;
//        n--;
//    }
//    while (tem)
//    {
//        int digit = tem % 10;
//        tem /= 10;
//        arr[i] = digit;
//        i++;
//    }
//    swap(arr, 0, i - 1);
//    *returnSize = i;
//    return arr;
//}
//													单链表
//typedef int SLTDateType;
//typedef struct SListNode
//{
//	SLTDateType data;
//	struct SListNode* next;
//}SListNode;
//
//// 动态申请一个节点
//SListNode* BuySListNode(SLTDateType x)
//{
//	SListNode* NewNode = (SListNode*)malloc(sizeof(SListNode));
//	assert(NewNode);
//	NewNode->data = x;
//	NewNode->next = NULL;
//	return NewNode;
//}
//// 单链表打印
//void SListPrint(SListNode* plist)
//{
//	if (plist==NULL)
//	{
//		printf("NULL\n");
//		return;
//	}
//	while (plist)
//	{
//		printf("%d->", plist->data);
//		plist = plist->next;
//	}
//	printf("NULL\n");
//}
//// 单链表尾插
//void SListPushBack(SListNode** pplist, SLTDateType x)
//{
//	SListNode* NewNode = BuySListNode(x);
//	SListNode* tail = *pplist;
//	if (tail == NULL)
//	{
//		printf("链表为空\n");
//		*pplist = NewNode;
//		return;
//	}
//	while (tail->next)
//	{
//		tail = tail->next;
//	}
//	tail->next = NewNode;
//}
//// 单链表的头插
//void SListPushFront(SListNode** pplist, SLTDateType x)
//{
//	SListNode*NewNode=BuySListNode(x);
//	SListNode* lend = *pplist;
//	NewNode->next = lend;
//	*pplist = NewNode;
//}
//// 单链表的尾删
//void SListPopBack(SListNode** pplist)
//{
//	if (*pplist == NULL)
//	{
//		printf("链表为空\n");
//		return;
//	}
//	SListNode* tail = *pplist;
//	SListNode* tem = tail;
//	while (tail->next)
//	{
//		tem = tail;
//		tail = tail->next;
//	}
//	tem->next = NULL;
//	free(tail);
//}
//// 单链表头删
//void SListPopFront(SListNode** pplist)
//{
//	if (*pplist == NULL)
//	{
//		printf("链表为空\n");
//		return;
//	}
//	SListNode* lend = *pplist;
//	*pplist = lend->next;
//}
//// 单链表查找
//SListNode* SListFind(SListNode* plist, SLTDateType x)
//{
//	if (plist == NULL)
//	{
//		printf("链表为空\n");
//		return NULL;
//	}
//	while (plist)
//	{
//		if (plist->data == x)
//		{
//			return plist;
//		}
//		plist = plist->next;
//	}
//	printf("没有找到\n");
//	return NULL;
//}
//// 单链表在pos位置之后插入x
//// 分析思考为什么不在pos位置之前插入？
////因为在pos位置之前插入需要遍历链表会增加时间复杂度
//void SListInsertAfter(SListNode* pos, SLTDateType x)
//{
//	assert(pos);
//	SListNode* NewNode =BuySListNode(x);
//	SListNode* next = pos->next;
//	pos->next = NewNode;
//	NewNode->next = next;
//}
//// 单链表删除pos位置之后的值
//// 分析思考为什么不删除pos位置？
////会增加时间复杂度
//void SListEraseAfter(SListNode* pos)
//{
//
//	if (pos==NULL)
//	{
//		printf("位置输入错误\n");
//		return;
//	}
//	SListNode* next = pos->next;
//	pos->next = next->next;
//}
//// 单链表的销毁
//void SListDestroy(SListNode* plist)
//{
//	if (plist==NULL)
//	{
//		printf("链表为空，不需要销毁\n");
//		return;
//	}
//	SListNode* cur = plist;
//	SListNode* next = cur;
//	while (cur)
//	{
//		if (next)
//		{
//			next = cur->next;
//		}
//		free(cur);
//		cur = next;
//	}
//	printf("销毁成功\n");
//}
//
//int main()
//{
//	SListNode* s1 = NULL;
//	SListPushFront(&s1, 1);
//	SListPushFront(&s1, 2);
//	SListPushFront(&s1, 3);
//	SListPushFront(&s1, 4);
//	SListPushFront(&s1, 5);
//	SListPrint(s1);
//
//	SListPushBack(&s1, 6);
//	SListPushBack(&s1, 6);
//	SListPushBack(&s1, 6);
//	SListPushBack(&s1, 6);
//	SListPrint(s1);
//
//	SListPopBack(&s1);
//	SListPopBack(&s1);
//	SListPopBack(&s1);
//	SListPopBack(&s1);
//	SListPopBack(&s1);
//	SListPrint(s1);
//
//	SListPopFront(&s1);
//	SListPopFront(&s1);
//	SListPopFront(&s1);
//	SListPrint(s1);
//
//	SListNode* tem = SListFind(s1, 2);
//	if (tem)
//	{
//		printf("%d\n", tem->data);
//	}
//	SListInsertAfter(SListFind(s1, 2), 5);
//	SListInsertAfter(SListFind(s1, 5), 6);
//	SListInsertAfter(SListFind(s1, 6), 7);
//	SListInsertAfter(SListFind(s1, 7), 8);
//	SListInsertAfter(SListFind(s1, 5), 100000);
//	SListPrint(s1);
//
//	SListEraseAfter(SListFind(s1, 2));
//	SListEraseAfter(SListFind(s1, 2));
//	SListEraseAfter(SListFind(s1, 10));
//	SListPrint(s1);
//
//	SListDestroy(s1);
//	return 0;
//}
//									移除链表元素
//struct ListNode* removeElements(struct ListNode* head, int val) {//遍历法
//    struct ListNode* cur = head;
//    struct ListNode* prev = NULL;
//    while (cur)
//    {
//        if (cur->val == val)
//        {
//            if (prev == NULL)
//            {
//                cur = cur->next;
//                head = cur;
//            }
//            else
//            {
//                cur = cur->next;
//                free(prev->next);
//                prev->next = cur;
//            }
//        }
//        else {
//            prev = cur;
//            cur = cur->next;
//        }
//    }
//    return head;
//}
// 
//struct ListNode* removeElements(struct ListNode* head, int val) {//尾插法
//    struct ListNode* cur = head;
//    struct ListNode* newhead = NULL;
//    struct ListNode* tail = NULL;
//    while (cur)
//    {
//        if (cur->val == val)
//        {
//            struct ListNode* tem = cur;
//            tem = cur->next;
//            free(cur);
//            cur = tem;
//        }
//        else
//        {
//            if (newhead == NULL)
//            {
//                newhead = cur;
//                tail = cur;
//                cur = cur->next;
//            }
//            else {
//                tail->next = cur;
//                tail = cur;
//                cur = cur->next;
//            }
//        }
//    }
//    if (tail)
//    {
//        tail->next = NULL;
//    }
//    return newhead;
//}
//                                              反转链表
//struct ListNode* reverseList(struct ListNode* head) {//反转法
//    struct ListNode* cur = head;
//    if (head == NULL || head->next == NULL)
//    {
//        return head;
//    }
//    struct ListNode* next = head->next;
//    struct ListNode* prev = NULL;
//    while (cur)
//    {
//        cur->next = prev;
//        prev = cur;
//        cur = next;
//        if (next)
//        {
//            next = next->next;
//        }
//    }
//    return prev;
//}
//
//struct ListNode* reverseList(struct ListNode* head) {//头插法
//    struct ListNode* cur = head;
//    struct ListNode* newhead = NULL;
//    struct ListNode* next = NULL;
//    while (cur)
//    {
//        next = cur->next;
//        cur->next = newhead;
//        newhead = cur;
//        cur = next;
//    }
//    return newhead;
//}
//								链表的中间结点
//struct ListNode* middleNode(struct ListNode* head) {
//	struct ListNode* fast = head;
//	struct ListNode* slow = head;
//	while (fast && fast->next)
//	{
//		fast = fast->next->next;
//		slow = slow->next;
//	}
//	return slow;
//}
//                                  链表中倒数第k个结点
//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//    struct ListNode* fast = pListHead;
//    struct ListNode* slow = pListHead;
//    int n = k;
//    while (n--)
//    {
//        if (fast == NULL)
//        {
//            return NULL;
//        }
//        fast = fast->next;
//    }
//    while (fast)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//    return slow;
//}
//                                              合并两个有序链表
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//带哨兵卫
//    struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
//    newnode->next = NULL;
//    struct ListNode* tail = newnode;
//    struct ListNode* cur1 = list1;
//    struct ListNode* cur2 = list2;
//    while (cur1 && cur2)
//    {
//        if (cur1->val < cur2->val)
//        {
//            tail->next = cur1;
//            tail = cur1;
//            cur1 = cur1->next;
//        }
//        else
//        {
//            tail->next = cur2;
//            tail = cur2;
//            cur2 = cur2->next;
//
//        }
//    }
//    if (cur2)
//    {
//        tail->next = cur2;
//    }
//    if (cur1)
//    {
//        tail->next = cur1;
//    }
//	  free(newnode);
//    return newnode->next;
//}
//
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//不带哨兵卫
//    struct ListNode* newnode = NULL;
//    struct ListNode* tail = NULL;
//    struct ListNode* cur1 = list1;
//    struct ListNode* cur2 = list2;
//    while (cur1 && cur2)
//    {
//        if (cur1->val < cur2->val)
//        {
//            if (newnode == NULL)
//            {
//                newnode = tail = cur1;
//                cur1 = cur1->next;
//            }
//            else
//            {
//                tail->next = cur1;
//                tail = cur1;
//                cur1 = cur1->next;
//            }
//        }
//        else
//        {
//            if (newnode == NULL)
//            {
//                newnode = tail = cur2;
//                cur2 = cur2->next;
//            }
//            else
//            {
//                tail->next = cur2;
//                tail = cur2;
//                cur2 = cur2->next;
//            }
//        }
//    }
//    if (cur2)
//    {
//        if (tail == NULL)
//        {
//            return cur2;
//        }
//        tail->next = cur2;
//    }
//    if (cur1)
//    {
//        if (tail == NULL)
//        {
//            return cur1;
//        }
//        tail->next = cur1;
//    }
//    return newnode;
//}
//                                          链表分割
//#include <cstdlib>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        ListNode* lesslist = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* gratelist = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* lesstail = lesslist;
//        ListNode* gratetail = gratelist;
//        ListNode* cur = pHead;
//        lesstail->next = NULL;
//        gratelist->next = NULL;
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                lesstail->next = cur;
//                lesstail = cur;
//                cur = cur->next;
//            }
//            else
//            {
//                gratetail->next = cur;
//                gratetail = cur;
//                cur = cur->next;
//            }
//        }
//        lesstail->next = gratelist->next;
//        gratetail->next = NULL;
//        return lesslist->next;
//    }
//};
////											链表的回文结构
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* A) {
//        ListNode* fast = A;
//        ListNode* slow = A;
//        while (fast && fast->next)
//        {
//            fast = fast->next->next;
//            slow = slow->next;
//        }
//        ListNode* list2 = slow;
//        ListNode* cur2 = list2;
//        while (cur2)
//        {
//            ListNode* next = cur2->next;
//            cur2->next = list2;
//            list2 = cur2;
//            cur2 = next;
//        }
//        slow->next = NULL;
//        ListNode* cur1 = A;
//        cur2 = list2;
//        while (cur2->next)
//        {
//            if (cur1->val != cur2->val)
//            {
//                return false;
//            }
//            else
//            {
//                cur1 = cur1->next;
//                cur2 = cur2->next;
//            }
//        }
//        return true;
//    }
//};
//												 链表相交
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    struct ListNode* cur1 = headA;
//    struct ListNode* cur2 = headB;
//    int sum1 = 1, sum2 = 1;
//    while (cur1)
//    {
//        cur1 = cur1->next;
//        sum1++;
//    }
//    while (cur2)
//    {
//        cur2 = cur2->next;
//        sum2++;
//    }
//    int sum = abs(sum1 - sum2);
//    cur1 = headA;
//    cur2 = headB;
//    if (sum1 > sum2)
//    {
//        while (sum--)
//        {
//            cur1 = cur1->next;
//        }
//    }
//    else
//    {
//        while (sum--)
//        {
//            cur2 = cur2->next;
//        }
//    }
//    while (1)
//    {
//        if (cur1 == NULL || cur2 == NULL)
//        {
//            return NULL;
//        }
//        if (cur1 != cur2)
//        {
//            cur1 = cur1->next;
//            cur2 = cur2->next;
//        }
//        else
//        {
//            return cur1;
//        }
//    }
//}
//                                          环形链表
//bool hasCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    while (1)
//    {
//        if (fast == NULL || fast->next == NULL)
//        {
//            return false;
//        }
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            return true;
//        }
//    }
//}
//// 带头+双向+循环链表增删查改实现
//typedef int LTDataType;
//typedef struct ListNode
//{
//	LTDataType _data;
//	struct ListNode* _next;
//	struct ListNode* _prev;
//}ListNode;
//
//// 创建返回链表的头结点.
//ListNode* ListCreate()
//{
//	ListNode* pHead = (ListNode*)malloc(sizeof(ListNode));
//	pHead->_next = pHead;
//	pHead->_prev = pHead;
//	return pHead;
//}
//
//ListNode* ByNewNode(LTDataType x)
//{
//	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
//	NewNode->_data = x;
//	NewNode->_next = NewNode;
//	NewNode->_prev = NewNode;
//	return NewNode;
//}
//
////判断链表是否为空
//bool Is_empty(ListNode* pHead)
//{
//	if (pHead->_next == pHead)
//	{
//		printf("链表为空\n");
//		return true;
//	}
//	else
//		return false;
//}
//
//// 双向链表销毁
//void ListDestory(ListNode* pHead)
//{
//	ListNode *cur=pHead->_next;
//	while (cur!=pHead)
//	{
//		ListNode* next = cur->_next;
//		free(cur);
//		cur = next;
//	}
//	printf("销毁成功\n");
//}
//// 双向链表打印
//void ListPrint(ListNode* pHead)
//{
//	assert(pHead);
//	ListNode* cur = pHead->_next;
//	while (cur != pHead)
//	{
//		printf("%d->", cur->_data);
//		cur = cur->_next;
//	}
//	printf("NULL\n");
//}
//// 双向链表尾插
//void ListPushBack(ListNode* pHead, LTDataType x)
//{
//	assert(pHead);
//	ListNode* NewNode = ByNewNode(x);
//	ListNode* tail = pHead->_prev;
//	NewNode->_next = pHead;
//	NewNode->_prev = tail;
//	tail->_next = NewNode;
//	pHead->_prev = NewNode;
//}
//// 双向链表尾删
//void ListPopBack(ListNode* pHead)
//{
//	assert(pHead);
//	
//	ListNode* tail = pHead->_prev;
//	pHead->_prev = tail->_prev;
//	tail->_prev->_next = pHead;
//	free(tail);
//}
//// 双向链表头插
//void ListPushFront(ListNode* pHead, LTDataType x)
//{
//	assert(pHead);
//	ListNode* NewNode = ByNewNode(x);
//	ListNode* head = pHead->_next;
//	NewNode->_next = head;
//	NewNode->_prev = pHead;
//	pHead->_next = NewNode;
//	head->_prev = NewNode;
//}
//// 双向链表头删
//void ListPopFront(ListNode* pHead)
//{
//	assert(pHead);
//	if (Is_empty(pHead))
//	{
//		return;
//	}
//	ListNode* head = pHead->_next;
//	pHead->_next = head->_next;
//	head->_next->_prev = pHead;
//	free(head);
//}
//// 双向链表查找
//ListNode* ListFind(ListNode* pHead, LTDataType x)
//{
//	assert(pHead);
//	if (Is_empty(pHead))
//	{
//		return NULL;
//	}
//	ListNode* cur = pHead->_next;
//	while (cur != pHead)
//	{
//		if (cur->_data == x)
//		{
//			return cur;
//		}
//		cur = cur->_next;
//	}
//	printf("没有找到\n");
//	return NULL;
//}
//// 双向链表在pos的前面进行插入
//void ListInsert(ListNode* pos, LTDataType x)
//{
//	assert(pos);
//	ListNode* prev = pos->_prev;
//	ListNode* NewNdoe = ByNewNode(x);
//	NewNdoe->_next = pos;
//	NewNdoe->_prev = prev;
//	prev->_next = NewNdoe;
//	pos->_prev = NewNdoe;
//}
//// 双向链表删除pos位置的节点
//void ListErase(ListNode* pos)
//{
//	if (Is_empty(pos))
//	{
//		return;
//	}
//	assert(pos);
//	pos->_prev->_next = pos->_next;
//	pos->_next->_prev = pos->_prev;
//	free(pos);
//}
//
//int main()
//{
//	ListNode* pHead = ListCreate();
//	ListPushBack(pHead, 1);
//	ListPushBack(pHead, 2);
//	ListPushBack(pHead, 3);
//	ListPushBack(pHead, 4);
//	ListPushBack(pHead, 5);
//	ListPrint(pHead);
//
//	ListPopBack(pHead);
//	ListPopBack(pHead);
//	ListPopBack(pHead);
//	ListPrint(pHead);
//
//	ListPushFront(pHead,4);
//	ListPushFront(pHead,3);
//	ListPushFront(pHead,2);
//	ListPushFront(pHead,1);
//	ListPrint(pHead);
//
//	ListPopFront(pHead);
//	ListPopFront(pHead);
//	ListPopFront(pHead);
//	ListPrint(pHead);
//
//	ListInsert(ListFind(pHead, 4), 10000);
//	ListPrint(pHead);
//
//	ListErase(ListFind(pHead, 4));
//	ListPrint(pHead);
//
//	ListDestory(pHead);
//	return 0;
//}
//                                                      环形链表 II
//struct ListNode* detectCycle(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    struct ListNode* cur = NULL;
//
//    while (1)
//    {
//        if (fast == NULL || fast->next == NULL)
//        {
//            return NULL;
//        }
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            break;
//        }
//    }
//    cur = fast;
//    struct ListNode* cur1 = head;
//    while (cur1 != cur)
//    {
//        cur1 = cur1->next;
//        cur = cur->next;
//    }
//    return cur;
//}
//                                              复制带随机指针的链表
//struct Node* copyRandomList(struct Node* head) {
//    struct Node* cur = head;
//    struct Node* copy = NULL;
//    struct Node* tail = NULL;
//    struct Node* newhead = NULL;
//    while (cur)
//    {
//        copy = (struct Node*)malloc(sizeof(struct Node));
//        struct Node* next = cur->next;
//        copy->val = cur->val;
//        cur->next = copy;
//        copy->next = next;
//        cur = next;
//    }
//    cur = head;
//    while (cur)
//    {
//        copy = cur->next;
//        if (cur->random == NULL)
//        {
//            copy->random = NULL;
//        }
//        else
//        {
//            copy->random = cur->random->next;
//        }
//        cur = copy->next;
//    }
//    cur = head;
//    while (cur)
//    {
//        copy = cur->next;
//        if (newhead == NULL)
//        {
//            newhead = tail = copy;
//        }
//        else
//        {
//            tail->next = copy;
//            tail = copy;
//        }
//        cur = copy->next;
//    }
//    return newhead;
//}
//															栈的实现
//typedef int StackType;
//typedef struct Stack
//{
//	StackType* data;
//	int top;
//	int capacity;
//}stack;
//
//
//void InitStack(stack* s1)//初始化栈
//{
//	s1->top = 0;
//	s1->capacity = 4;
//	s1->data = (StackType*)malloc(sizeof(StackType)*s1->capacity);
//	if (s1->data == NULL)
//	{
//		printf("开辟空间失败\n");
//		exit (-1);
//	}
//}
//
//void pushStack(stack* s1, StackType x)//入栈
//{
//	if (s1->top == s1->capacity)
//	{
//		StackType* newdata = (StackType*)realloc(s1->data, (s1->capacity += 4) * sizeof(StackType));
//		if (newdata != NULL)
//		{
//			s1->data = newdata;
//		}
//		else
//		{
//			printf("扩容失败\n");
//			exit(-1);
//		}
//	}
//	s1->data[s1->top] = x;
//	s1->top++;
//}
//
//void popStack(stack* s1)//出栈
//{
//	if (s1->top != 0)
//	{
//		s1->top--;
//	}
//	else
//	{
//		printf("栈为空\n");
//		return;
//	}
//}
//
//StackType StackTop(stack* s1)//获取栈顶元素
//{
//	assert(s1);
//	if (s1->top != 0)
//	{
//		return s1->data[s1->top-1];
//	}
//	else
//	{
//		printf("栈为空\n");
//		return EOF;
//	}
//}
//int StackSize(stack* ps)//获取栈中有效元素个数
//{
//	assert(ps);
//	printf("%d\n", ps->top);
//	return ps->top;
//}
//
//// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
//int StackEmpty(stack* ps)
//{
//	if (ps->top == 0)
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}
//
//// 销毁栈 
//void StackDestroy(stack* ps)
//{
//	if (ps->top != 0)
//	{
//		free(ps->data);
//		ps->data = NULL;
//		printf("销毁成功\n");
//	}
//	else
//	{
//		printf("栈为空，不需要销毁\n");
//		return;
//	}
//}
//
//int main()
//{
//	int s[] = { 1,2,3,4,5,6,7,8,9 };
//	stack s1;
//	InitStack(&s1);
//	printf("%d\n", StackEmpty(&s1));
//	pushStack(&s1, 5);
//	printf("%d\n", StackTop ( & s1));
//	pushStack(&s1, 4);
//	pushStack(&s1, 3);
//	pushStack(&s1, 2);
//	pushStack(&s1, 1);
//	printf("%d\n", StackEmpty(&s1));
//
//	printf("%d\n", StackTop(&s1));
//	StackSize(&s1);
//
//	StackDestroy(&s1);
//	return 0;
//}
//															链式结构：表示队列
//typedef int QDataType;
//typedef struct QListNode
//{
//	struct QListNode* _next;
//	QDataType _data;
//}QNode;
//
//// 队列的结构 
//typedef struct Queue
//{
//	QNode* _front;
//	QNode* _rear;
//}Queue;
//
//// 初始化队列 
//void QueueInit(Queue* q)
//{
//	assert(q);
//	QNode* listhead = (QNode*)malloc(sizeof(QNode));
//	if (listhead == NULL)
//	{
//		printf("初始化队列失败\n");
//		exit(-1);
//	}
//	listhead->_next = NULL;
//	q->_front = listhead;
//	q->_rear = listhead;
//}
//// 队尾入队列 
//void QueuePush(Queue* q, QDataType data)
//{
//	QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
//	if (newnode == NULL)
//	{
//		printf("开辟空间失败\n");
//		exit(-1);
//	}
//	newnode->_data = data;
//	newnode->_next = NULL;
//	q->_rear->_next = newnode;
//	q->_rear = newnode;
//}
//// 队头出队列 
//void QueuePop(Queue* q)
//{
//	assert(q);
//	if (q->_front->_next == NULL)
//	{
//		printf("队列为空，无法出列\n");
//		return;
//	}
//	if (q->_front->_next == q->_rear)
//	{
//		free(q->_rear);
//		q->_front->_next = NULL;
//		q->_rear = q->_front;
//	}
//	else
//	{
//		QNode* head = q->_front->_next;
//		QNode* next = head->_next;
//		q->_front->_next = next;
//		free(head);
//	}
//}
//// 获取队列头部元素 
//QDataType QueueFront(Queue* q)
//{
//	assert(q);
//	if (q->_front->_next!=NULL)
//	return q->_front->_next->_data;
//	else
//	{
//		printf("队列为空，没有元素\n");
//		return EOF;
//	}
//}
//// 获取队列队尾元素 
//QDataType QueueBack(Queue* q)
//{
//	if (q->_front->_next == NULL)
//	{
//		printf("队列为空\n");
//		return EOF;
//	}
//	else
//	{
//		return q->_rear->_data;
//	}
//}
//// 获取队列中有效元素个数 
//int QueueSize(Queue* q)
//{
//	QNode* cur = q->_front->_next;
//	int sum = 0;
//	while (cur)
//	{
//		cur = cur->_next;
//		sum++;
//	}
//	return sum;
//}
//// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
//int QueueEmpty(Queue* q)
//{
//	assert(q);
//	if (q->_front->_next == NULL)
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//}
//// 销毁队列 
//void QueueDestroy(Queue* q)
//{
//	QNode* cur = q->_front;
//	while (cur)
//	{
//		QNode* next = cur->_next;
//		free(cur);
//		cur = next;
//	}
//	printf("销毁成功\n");
//}
//
//int main()
//{
//	Queue s1;
//	QueueInit(&s1);
//	QueuePush(&s1, 1);
//	QueuePush(&s1, 2);
//	QueuePush(&s1, 3);
//	QueuePush(&s1, 4);
//	QueuePush(&s1, 5);
//
//	printf("%d\n",QueueFront(&s1));
//
//	
//	QueuePop(&s1);
//	printf("%d\n", QueueFront(&s1));
//
//	printf("%d\n", QueueSize(&s1));
//
//	QueueDestroy(&s1);
//	return 0;
//}
//													用队列实现栈
//typedef struct {
//    Queue q1;
//    Queue q2;
//
//
//} MyStack;
//
//
//MyStack* myStackCreate() {
//    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
//    QueueInit(&obj->q1);
//    QueueInit(&obj->q2);
//    return obj;
//}
//
//void myStackPush(MyStack* obj, int x) {
//    if (!QueueEmpty(&obj->q1))
//    {
//        QueuePush(&obj->q1, x);
//    }
//    else {
//        QueuePush(&obj->q2, x);
//    }
//}
//
//int myStackPop(MyStack* obj) {
//    if (!QueueEmpty(&obj->q1))
//    {
//        while (QueueSize(&obj->q1) > 1)
//        {
//            QueuePush(&obj->q2, QueueFront(&obj->q1));
//            QueuePop(&obj->q1);
//        }
//        int ret = QueueBack(&obj->q1);
//        QueuePop(&obj->q1);
//        return ret;
//    }
//    else
//    {
//        while (QueueSize(&obj->q2) > 1)
//        {
//            QueuePush(&obj->q1, QueueFront(&obj->q2));
//            QueuePop(&obj->q2);
//        }
//        int ret = QueueBack(&obj->q2);
//        QueuePop(&obj->q2);
//        return ret;
//    }
//}
//
//int myStackTop(MyStack* obj) {
//    if (!QueueEmpty(&obj->q1))
//    {
//        return QueueBack(&obj->q1);
//    }
//    else
//    {
//        return QueueBack(&obj->q2);
//    }
//}
//
//bool myStackEmpty(MyStack* obj) {
//    if (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
//    {
//        return true;
//    }
//    return false;
//}
//
//void myStackFree(MyStack* obj) {
//    QueueDestroy(&obj->q1);
//    QueueDestroy(&obj->q2);
//    free(obj);
//}
//														用两个栈表示队列
//typedef struct {
//    stack addstack;
//    stack delstack;
//} MyQueue;
//
//
//MyQueue* myQueueCreate() {
//    MyQueue* obj = malloc(sizeof(MyQueue));
//    InitStack(&obj->addstack);
//    InitStack(&obj->delstack);
//    return obj;
//}
//
//void myQueuePush(MyQueue* obj, int x) {
//    pushStack(&obj->addstack, x);
//}
//
//int myQueuePop(MyQueue* obj) {
//    if (StackEmpty(&obj->delstack))
//    {
//        while (StackSize(&obj->addstack) > 0)
//        {
//            pushStack(&obj->delstack, StackTop(&obj->addstack));
//            popStack(&obj->addstack);
//        }
//        int ret = StackTop(&obj->delstack);
//        popStack(&obj->delstack);
//        return ret;
//    }
//    else
//    {
//        int ret = StackTop(&obj->delstack);
//        popStack(&obj->delstack);
//        return ret;
//    }
//}
//
//int myQueuePeek(MyQueue* obj) {
//    if (StackEmpty(&obj->delstack))
//    {
//        while (StackSize(&obj->addstack) > 0)
//        {
//            pushStack(&obj->delstack, StackTop(&obj->addstack));
//            popStack(&obj->addstack);
//        }
//    }
//    return StackTop(&obj->delstack);
//}
//
//bool myQueueEmpty(MyQueue* obj) {
//    return StackEmpty(&obj->addstack) && StackEmpty(&obj->delstack);
//}
//
//void myQueueFree(MyQueue* obj) {
//    StackDestroy(&obj->addstack);
//    StackDestroy(&obj->delstack);
//    free(obj);
//}
//												循环队列
//typedef struct {
//    int head;
//    int tail;
//    int* data;
//    int k;
//} MyCircularQueue;
//
//
//MyCircularQueue* myCircularQueueCreate(int k) {
//    MyCircularQueue* obj = malloc(sizeof(MyCircularQueue));
//    if (obj == NULL)
//    {
//        printf("开辟空间失败\n");
//        exit(-1);
//    }
//    obj->head = 0;
//    obj->tail = 0;
//    obj->k = k;
//    obj->data = malloc(sizeof(int) * (k + 1));
//    if (obj->data == NULL)
//    {
//        printf("开辟空间失败\n");
//        exit(-1);
//    }
//    return obj;
//}
//
//bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//    int a = (obj->tail + 1) % (obj->k + 1);
//    if (obj->head != a)
//    {
//        obj->data[obj->tail] = value;
//        obj->tail++;
//        obj->tail %= (obj->k + 1);
//        return true;
//    }
//    else
//    {
//        return false;
//    }
//}
//
//bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//    if (obj->head != obj->tail)
//    {
//        obj->head++;
//        obj->head %= (obj->k + 1);
//        return true;
//    }
//    else {
//        return false;
//    }
//}
//
//int myCircularQueueFront(MyCircularQueue* obj) {
//    if (obj->head == obj->tail)
//    {
//        return -1;
//    }
//    else {
//        return obj->data[obj->head];
//    }
//}
//
//int myCircularQueueRear(MyCircularQueue* obj) {
//    if (obj->head == obj->tail)
//    {
//        return -1;
//    }
//    int a = obj->tail - 1;
//    if (a == -1)
//    {
//        return obj->data[obj->k];
//    }
//    else
//    {
//        return obj->data[obj->tail - 1];
//    }
//}
//
//bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//    if (obj->tail == obj->head)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}
//
//bool myCircularQueueIsFull(MyCircularQueue* obj) {
//    int a = (obj->tail + 1) % (obj->k + 1);
//    if (obj->head == a)
//    {
//        return true;
//    }
//    else {
//        return false;
//    }
//}
//
//void myCircularQueueFree(MyCircularQueue* obj) {
//    free(obj->data);
//    free(obj);
//}
//												链表插入排序
//struct ListNode* insertionSortList(struct ListNode* head) {
//    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* cur = head;
//    struct ListNode* next = NULL;
//    struct ListNode* tail = NULL;
//    while (cur)
//    {
//        if (cur == head)
//        {
//            next = cur->next;
//            newhead->next = tail = cur;
//            tail->next = NULL;
//            cur = next;
//        }
//        else
//        {
//            struct ListNode* cur1 = newhead->next;
//            struct ListNode* prev = newhead;
//            int judge = 0;
//            while (cur1)
//            {
//                if (cur->val <= cur1->val)
//                {
//                    next = cur->next;
//                    prev->next = cur;
//                    cur->next = cur1;
//                    cur = next;
//                    judge = 1;
//                    break;
//                }
//                prev = cur1;
//                cur1 = cur1->next;
//            }
//            if (judge == 0)
//            {
//                next = cur->next;
//                tail->next = cur;
//                tail = cur;
//                tail->next = NULL;
//                cur = next;
//            }
//        }
//    }
//
//    return newhead->next;
//}
//															删除链表中的重复节点
//struct ListNode* deleteDuplication(struct ListNode* pHead) {
//    struct ListNode* newhead = NULL;
//    if (pHead == NULL || pHead->next == NULL)
//    {
//        return pHead;
//    }
//    struct ListNode* tail = NULL;
//    struct ListNode* next = NULL;
//    struct ListNode* cur = pHead;
//    int ret = -1;
//    while (cur)
//    {
//        next = cur->next;
//        if (next != NULL && cur->val == next->val)
//        {
//            ret = cur->val;
//
//        }
//        else if (ret != cur->val)
//        {
//            if (newhead == NULL)
//            {
//                newhead = tail = cur;
//                tail->next = NULL;
//            }
//            else {
//                tail->next = cur;
//                tail = cur;
//                tail->next = NULL;
//            }
//        }
//        cur = next;
//    }
//
//    return newhead;
//}

//													 堆的实现
//#include<stdio.h>
//#include<malloc.h>
//#include<stdlib.h>
//#include<assert.h>
//typedef int HPDataType;
//typedef struct Heap
//{
//	HPDataType* _a;
//	int _size;
//	int _capacity;
//}Heap;
//
//// 堆的构建
//void HeapInIt(Heap* hp)
//{
//	hp->_capacity = 4;
//	hp->_size = 0;
//	hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * hp->_capacity);
//}
//// 堆的销毁
//void HeapDestory(Heap* hp)
//{
//	if (hp->_a != NULL)
//	{
//		free(hp->_a);
//	}
//}
//
//// 堆的判空
//int HeapEmpty(Heap* hp)
//{
//	if (hp->_size == 0)
//	{
//		return 1;
//	}
//	else
//		return 0;
//}
//
////交换
//void swap(HPDataType* a, HPDataType* b)
//{
//	HPDataType tem = *a;
//	*a = *b;
//	*b = tem;
//}
//
////向下调整(当我们根节点下方数据全部不为堆时我们调整堆需要是从最后一个非叶子结点开始)
//void adjustdown(HPDataType* a, int p, int size)
//{
//	int child = p * 2 + 1;
//	while (child < size)
//	{
//		if (child + 1 < size && a[child + 1] < a[child])
//		{
//			child = child + 1;
//		}
//		if (a[child] < a[p])
//		{
//			swap(&a[child], &a[p]);
//		}
//		else
//		{
//			break;
//		}
//		p = child;
//		child = p * 2 + 1;
//	}
//}
//
////向上调整
//void adjustup(HPDataType* a, int c)
//{
//	int p = (c - 1) / 2;
//	while (c > 0)
//	{
//		if (a[c] < a[p])
//		{
//			swap(&a[c], &a[p]);
//		}
//		else
//		{
//			break;
//		}
//		c = p;
//		p = (c - 1) / 2;
//	}
//}
//
//// 堆的插入
//void HeapPush(Heap* hp, HPDataType x)
//{
//	assert(hp);
//	if (hp->_size == hp->_capacity)
//	{
//		HPDataType* x = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * (hp->_capacity += 4));
//		if (x == NULL)
//		{
//			printf("realloc fail  1052");
//			exit(-1);
//		}
//		hp->_a = x;
//	}
//	hp->_a[hp->_size] = x;
//	hp->_size++;
//	adjustup(hp->_a, hp->_size - 1);
//}
//// 堆的删除
//void HeapPop(Heap* hp)
//{
//	assert(hp);
//	swap(&hp->_a[hp->_size - 1], &hp->_a[0]);
//	adjustdown(hp->_a, 0, hp->_size - 1);
//	hp->_size--;
//}
//// 取堆顶的数据
//HPDataType HeapTop(Heap* hp)
//{
//	if (!HeapEmpty(hp))
//	{
//		return hp->_a[0];
//	}
//	printf("堆为空，无法打印\n");
//	return EOF;
//}
//// 堆的数据个数
//int HeapSize(Heap* hp)
//{
//	assert(hp);
//	return hp->_size;
//}
//
////建堆
//void HeapCreate(HPDataType* a, int size)
//{
//	int i = 0;
//	for (i = (size - 1 - 1) / 2; i >= 0; i--)
//	{
//		adjustdown(a, i, size);
//	}
//}
//
//// TopK问题：找出N个数里面最大/最小的前K个问题。
//// 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，全国排名前10的李白。等等问题都是Topk问题，
//// 需要注意：
//// 找最大的前K个，建立K个数的小堆
//// 找最小的前K个，建立K个数的大堆
//void PrintTopK(int* a, int n, int k)
//{
//	int i,size=k;
//	for (i = 0; i < size;)
//	{
//		swap(&a[0], &a[size - 1]);
//		size--;
//		adjustdown(a, 0, size);
//	}
//	for (i = 0; i < k; i++)
//	{
//		printf("%d ", a[i]);
//	}
//}
//void TestTopk(int* a, int n, int k)
//{
//	int i = 0;
//	for (i = (k - 1 - 1) / 2; i >= 0; i--)
//	{
//		adjustdown(a, i, k);
//	}
//	int j = k;
//	while (j < n)
//	{
//		if (a[j] > a[0])
//		{
//			swap(&a[j], &a[0]);
//			adjustdown(a, 0, k);
//		}
//		j++;
//	}
//}
//
//int main()
//{
//	Heap hp;
//	int i = 0, size, c[10000],b;
//	int a[] = { 5,8,9,4,6,8,2,6,4,8,1 };
//	srand(unsigned int(time(NULL)));
//	for (i = 0; i < 10000; i++)
//	{
//		c[i] = rand() % 10000;
//	}
//	c[25] = 10000 + 1;
//	c[646] = 10000 + 2;
//	c[4564] = 10000 + 3;
//	c[2169] = 10000 + 4;
//	c[8] = 10000 + 5;
//	TestTopk(c, 10000, 5);
//	PrintTopK(c, 10000, 5);
//	//b = size = sizeof(a) / sizeof(a[0]);
//	//HeapCreate(a, size);
//	//for (i = 0; i < size;)
//	//{
//	//	swap(&a[0], &a[size - 1]);
//	//	size--;
//	//	adjustdown(a, 0, size);
//	//}
//	//for (i = 0; i < b; i++)
//	//{
//	//	printf("%d ", a[i]);
//	//}
//	//	HeapCreate(&hp);
//	//	for (i = 0; i <hp._size; i++)
//	//	{
//	//		HeapPush(&hp, a[i]);
//	//	}
//	//	HeapPop(&hp);
//	//	printf("%d\n", HeapSize(&hp));
//	//	printf("%d\n", HeapTop(&hp));
//	return 0;
//}

//												二叉树的实现
//typedef char BTDataType;
//
//typedef struct BinaryTreeNode
//{
//	BTDataType _data;
//	struct BinaryTreeNode* _left;
//	struct BinaryTreeNode* _right;
//}BTNode;
//
//typedef BTNode dataType;
////创建节点
//BTNode* BuyNode(BTDataType data)
//{
//	BTNode* p = (BTNode*)malloc(sizeof(BTNode));
//	assert(p);
//	p->_left = NULL;
//	p->_right = NULL;
//	p->_data = data;
//	return p;
//}
//
////构建二叉树
//BTNode* BinaryTreeCreate()
//{
//	BTNode* p1 = BuyNode('A');
//	BTNode* p2 = BuyNode('B');
//	BTNode* p3 = BuyNode('C');
//	BTNode* p4 = BuyNode('D');
//	BTNode* p5 = BuyNode('E');
//	BTNode* p6 = BuyNode('F');
//	BTNode* p7 = BuyNode('G');
//	BTNode* p8 = BuyNode('H');
//	BTNode* p9 = BuyNode('I');
//	p1->_left = p2;
//	p1->_right = p3;
//	p2->_left = p4;
//	p2->_right = p5;
//	p3->_left = p6;;
//	p3->_right = p7;
//	//p5->_right = p8;
//	//p4->_left = p9;
//	return p1;
//}
//// 二叉树销毁
//void BinaryTreeDestory(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	BinaryTreeDestory(root->_left);
//	BinaryTreeDestory(root->_right);
//	free(root);
//}
//// 二叉树节点个数
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
//}
//// 二叉树叶子节点个数
//int BinaryTreeLeafSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	if (root->_left == NULL && root->_right == NULL)
//		return 1;
//	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
//}
//// 二叉树第k层节点个数
//int BinaryTreeLevelKSize(BTNode* root, int k)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	if (k == 1)
//	{
//		return 1;
//	}
//	return BinaryTreeLevelKSize(root->_left,k-1) + BinaryTreeLevelKSize(root->_right,k-1);
//}
//
//// 二叉树前序遍历 
//void BinaryTreePrevOrder(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("#");
//		return ;
//	}
//	printf("%c", root->_data);
//	BinaryTreePrevOrder(root->_left);
//	BinaryTreePrevOrder(root->_right);
//}
//// 二叉树中序遍历
//void BinaryTreeInOrder(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("#");
//		return;
//	}
//	BinaryTreePrevOrder(root->_left);
//	printf("%c", root->_data);
//	BinaryTreePrevOrder(root->_right);
//}
//// 二叉树后序遍历
//void BinaryTreePostOrder(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("#");
//		return;
//	}
//	BinaryTreePrevOrder(root->_left);
//	BinaryTreePrevOrder(root->_right);
//	printf("%c", root->_data);
//}
//
//
//// 二叉树查找值为x的节点
//
//void Find(BTNode* root, BTDataType x, BTNode** find)
//{
//	if (root == NULL)
//		return;
//	if (root->_data == x)
//	{
//		*find = root;
//	}
//	Find(root->_left, x, find);
//	Find(root->_right, x, find);
//}
//
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//	if (root == NULL)
//	{
//		printf("树为空树\n");
//		return NULL;
//	}
//	BTNode* find = NULL;
//	Find(root, x, &find);
//	if (find != NULL)
//	{
//		printf("找到了\n");
//		return find;
//	}
//	printf("没找到\n");
//	return NULL;
//}
//
//
//// 层序遍历
//
//typedef struct SList
//{
//	dataType* data;
//	struct SList* next;
//}slist;
//
//
//typedef struct Queue
//{
//	slist* head;
//	slist* tail;
//}queue;
//
//void cratequeue(queue* p1)
//{
//	p1->head = p1->tail = NULL;
//}
//
//slist* buynode(queue* p1, dataType* data)
//{
//	slist* newnode = (slist*)malloc(sizeof(slist));
//	if (newnode != NULL)
//	{
//		newnode->data = data;
//		newnode->next = NULL;
//		return newnode;
//	}
//	else
//	{
//		printf("malloc fail\n");
//		exit(-1);
//	}
//}
//
//void PushQueue(queue* p1, dataType* data)
//{
//	slist* newnode = buynode(p1, data);
//	if (p1->head == NULL)
//	{
//		p1->head = p1->tail = newnode;
//	}
//	else
//	{
//		p1->tail->next = newnode;
//		p1->tail = newnode;
//	}
//}
//
//void PopQueue(queue* p1)
//{
//	if (p1->head == NULL)
//	{
//		printf("队列为空\n");
//		return;
//	}
//	slist* next = p1->head->next;
//	free(p1->head);
//	p1->head = next;
//}
//
//void DistroyQueque(queue* p1)
//{
//	if (p1->head == NULL)
//	{
//		printf("队列为空，无需摧毁\n");
//	}
//	while (p1->head)
//	{
//		slist* next = p1->head->next;
//		free(p1->head);
//		p1->head = next;
//	}
//	printf("摧毁成功\n");
//}
//
//slist* queuehead(queue* p1)
//{
//	return p1->head;
//}
//
//void BinaryTreeLevelOrder(BTNode* root)
//{
//	if (root == NULL)
//		return;
//	queue p1;
//	cratequeue(&p1);
//	PushQueue(&p1, root);
//	while (p1.head != NULL)
//	{
//		slist* cur = queuehead(&p1);
//		printf("%c ", cur->data->_data);
//		if (cur->data->_left != NULL)
//		{
//			PushQueue(&p1, cur->data->_left);
//		}
//		if (cur->data->_right != NULL)
//		{
//			PushQueue(&p1, cur->data->_right);
//		}
//		PopQueue(&p1);
//	}
//	DistroyQueque(&p1);
//}
//
//// 判断二叉树是否是完全二叉树
//int BinaryTreeComplete(BTNode* root)
//{
//	if (root == NULL)
//		return 1;
//	queue p1;
//	cratequeue(&p1);
//	PushQueue(&p1, root);
//	int tag = 0;
//	while (p1.head != NULL)
//	{
//		slist* cur = queuehead(&p1);
//		printf("%c ", cur->data->_data);
//		if (cur->data->_left)
//		{
//			if (tag == 1)
//				return 0;
//			PushQueue(&p1, cur->data->_left);
//		}
//		else
//			tag = 1;
//		if (cur->data->_right)
//		{
//			if (tag == 1)
//				return 0;
//			PushQueue(&p1, cur->data->_right);
//		}
//		else
//			tag = 1;
//		PopQueue(&p1);
//	}
//	DistroyQueque(&p1);
//	return 1;
//}
//
//int main()
//{
//	BTNode *root=BinaryTreeCreate();
////	BinaryTreePrevOrder(root);
////	printf("\n");
////	printf("%d\n", BinaryTreeSize(root));
////	printf("%d\n", BinaryTreeLeafSize(root));
////	printf("%d\n", BinaryTreeLevelKSize(root,1));
////	printf("%d\n", BinaryTreeLevelKSize(root, 2));
////	printf("%d\n", BinaryTreeLevelKSize(root, 3));
////	printf("%d\n", BinaryTreeLevelKSize(root, 4));
////	printf("%d\n", BinaryTreeLevelKSize(root, 5));
////	BinaryTreeLevelOrder(root);
////	BinaryTreeFind(root, 'A');
//	if (BinaryTreeComplete(root) == 0)
//	{
//		printf("不完全二叉树\n");
//	}
//	else
//		printf("完全二叉树\n");
//	BinaryTreeDestory(root);
//	return 0;
//}

//后续遍历
//int Size(struct TreeNode* root)
//{
//    if (root == NULL)
//        return 0;
//    return Size(root->left) + Size(root->right) + 1;
//}
//void InItarr(struct TreeNode* root, int* size, int* a)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    InItarr(root->left, size, a);
//    InItarr(root->right, size, a);
//    printf("%d ", *size);
//    a[*size] = root->val;
//    (*size)++;
//}
//int* postorderTraversal(struct TreeNode* root, int* returnSize) {
//    *returnSize = Size(root);
//    int i = 0;
//    int* a = (int*)malloc(sizeof(int) * (*returnSize));
//    InItarr(root, &i, a);
//    return a;
//}

//                                              单值二叉树
// 法一
//bool isUnivalTree(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return true;
//    }
//    if (root->left && root->val != root->left->val)
//    {
//        return false;
//    }
//    if (root->right && root->val != root->right->val)
//    {
//        return false;
//    }
//    return isUnivalTree(root->left) && isUnivalTree(root->right);
//}

////法二
//bool judge(struct TreeNode* root, int val)
//{
//    if (root == NULL)
//    {
//        return true;
//    }
//    if (root->val != val)
//        return false;
//    return judge(root->left, val) && judge(root->right, val);
//}
//
//bool isUnivalTree(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return true;
//    }
//    return judge(root, root->val);
//}

//                                                          树的深度
//int depth(struct TreeNode* root)
//{
//    if (root == NULL)
//        return 0;
//    int left = 1 + depth(root->left);
//    int right = 1 + depth(root->right);
//    if (left > right)
//        return left;
//    else
//        return right;
//}
//int maxDepth(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return 0;
//    }
//    return depth(root);
//}

//													相同的树
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//	if (p == NULL && q == NULL)
//		return true;
//	if (p == NULL || q == NULL)
//		return false;
//	if (p->val != q->val)
//		return false;
//	bool a = isSameTree(p->left, q->left);
//	bool b = isSameTree(p->right, q->right);
//	return a && b;
//}
//														对称二叉树
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//        return true;
//    if (p == NULL || q == NULL)
//        return false;
//    if (p->val != q->val)
//        return false;
//    bool a = isSameTree(p->left, q->right);
//    bool b = isSameTree(p->right, q->left);
//    return a && b;
//}
//bool isSymmetric(struct TreeNode* root) {
//    if (root == NULL)
//        return true;
//    return isSameTree(root->left, root->right);
//}

//														二叉树的子树
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//    if (p == NULL && q == NULL)
//        return true;
//    if (p == NULL || q == NULL)
//        return false;
//    if (p->val != q->val)
//        return false;
//    bool a = isSameTree(p->left, q->left);
//    bool b = isSameTree(p->right, q->right);
//    return a && b;
//}
//
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
//    if (root == NULL)
//        return false;
//    if (isSameTree(root, subRoot))
//        return true;
//    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}

////                                                  反转二叉树
//void reversal(struct TreeNode* root)
//{
//    if (root == NULL)
//        return;
//    struct TreeNode* tem;
//    tem = root->left;
//    root->left = root->right;
//    root->right = tem;
//    reversal(root->left);
//    reversal(root->right);
//}
//struct TreeNode* invertTree(struct TreeNode* root) {
//    reversal(root);
//    return root;
//}

//													平衡二叉树
//int depth(struct TreeNode* root)
//{
//    if (root == NULL)
//        return 0;
//    int left = 1 + depth(root->left);
//    int right = 1 + depth(root->right);
//    if (left > right)
//        return left;
//    else
//        return right;
//}
//bool isBalanced(struct TreeNode* root) {
//    if (root == NULL)
//        return true;
//    int a = abs(depth(root->left) - depth(root->right));
//    if (a > 1)
//        return false;
//    return isBalanced(root->left) && isBalanced(root->right);
//}

//																二叉树遍历
//#include <stdio.h>
//#include<assert.h>
//typedef char DataType;
//typedef struct BinaryTreeNode {
//    DataType data;
//    struct BinaryTreeNode* left;
//    struct BinaryTreeNode* right;
//} BTNode;
//
//BTNode* BuyNode(char* a, int* pi) {
//    BTNode* p = (BTNode*)malloc(sizeof(BTNode));
//    assert(p);
//    p->left = NULL;
//    p->right = NULL;
//    p->data = *(a + *pi);
//    return p;
//}
//
//BTNode* cratetree(char* a, int* pi) {
//    if (*(a + *pi) != '#') {
//        BTNode* root = BuyNode(a, pi);
//        (*pi)++;
//        root->left = cratetree(a, pi);
//        (*pi)++;
//        root->right = cratetree(a, pi);
//        return root;
//    }
//    else {
//        return NULL;
//    }
//}
//
//void PrintTree(BTNode* root)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    PrintTree(root->left);
//    printf("%c ", root->data);
//    PrintTree(root->right);
//}
//
//int main() {
//    char arr[10000];
//    int pi = 0;
//    scanf(" %s", arr);
//    BTNode* root = cratetree(arr, &pi);
//    PrintTree(root);
//    return 0;
//}

//												括号问题（学校oj）
//void test()
//{
//    char* a = (char*)malloc(sizeof(char) * 105);
//    memset(a, '\0', sizeof(char) * 105);
//    stack p1;
//    while (gets(a) != NULL)
//    {
//        printf("%s\n", a);
//        int i = 0, j = 0;
//        char count = '0';
//        InitStack(&p1);
//        while (a[j] != '\0')
//        {
//            if (a[j] == '(')
//            {
//                count = j + '0';
//                a[j] = count;
//                pushStack(&p1, count);
//            }
//            else if (a[j] >= 'A' && a[j] <= 'Z' || a[j] >= 'a' && a[j] <= 'z')
//            {
//                a[j] = ' ';
//            }
//            else if (a[j] == ')')
//            {
//                if (!StackEmpty(&p1))
//                {
//                    char n = StackTop(&p1);
//                    int m = n - '0';
//                    a[m] = ' ';
//                    popStack(&p1);
//                    a[j] = ' ';
//                }
//                else
//                {
//                    a[j] = '?';
//                }
//            }
//            j++;
//        }
//        while (!StackEmpty(&p1))
//        {
//            char n = StackTop(&p1);
//            int m = n - '0';
//            a[m] = '$';
//            popStack(&p1);
//        }
//        printf("%s\n", a);
//        StackDestroy(&p1);
//    }
//}

//														引用测试
//int& a(int& b)
//{
//	b = 4;
//	return b;
//}
//int main()
//{
//	int b = 1;
//	a(b) = 5;
//	printf("%d\n", a(b));
//	std::cout << a(b) << std::endl;
//	return 0;
//}

//namespace myspace
//{
//	int Add(int a, int b)
//	{
//		return a + b;
//	}
//}
//
//using namespace std;
//int main()
//{
//	
//	int a = 10;
//	int& ra = a;//<====定义引用类型
//	printf("%p\n", &a);
//	printf("%p\n", &ra);
//	return 0;
//}

//using namespace std;
// inline int Add(int a, int b)
//{
//	return a + b;
//}
//
//void TestFor()
//{
//	 int array[] = { 1, 2, 3, 4, 5 };
//	 for (auto& e : array)
//		 e *= 2;
//	 for (auto e : array)
//		 cout << e << " ";
//}
//int main()
//{
//	TestFor();
//	return 0;
//}

//using namespace std;
//class Date
//{
//public:
//	void Init(int year, int month, int day)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//	void Print()
//	{
//		cout << this << endl;
//		cout << _year << "-" << _month << "-" << _day << endl;
//	}
//private:
//	int _year;     // 年   -> 声明
//	int _month;    // 月
//	int _day;      // 日
//};
//int main()
//{
//	Date d1;
//	d1.Init(2022, 5, 30);
//	d1.Print();
//	printf("%p", &d1);
//	return 0;
//}
//
//class Date
//{
//public:
//	Date()//无参构造函数
//	{
//		_year = 1900;
//		_month = 1;
//		_day = 1;
//	}
//	Date(int year = 1900, int month = 1, int day = 1)//全缺省构造函数
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//
//class Time
//{
//public:
//	Time()
//	{
//		cout << "Time()" << endl;
//		_hour = 0;
//		_minute = 0;
//	}
//private:
//	int _hour;
//	int _minute;
//	int _second;
//};
//class Date
//{
//private:
//	// 基本类型(内置类型)
//	int _year = 1970;
//	int _month = 1;
//	int _day = 1;
//	// 自定义类型
//	Time _t;
//};

////下面证明了我们没有在类中声明的函数是无法用使用类来
//class Date
//{
//public:
//	Date(int year = 1900, int month = 1, int day = 1)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//	int _year;
//	int _month;
//	int _day;
//};
//
//Date& a1:operator=( const Date& right)
//{
//	if (this != &right)
//	{
//		_year = right._year;
//		_month = right._month;
//		_day = right._day;
//	}
//	return *this;
//}
//
//int main()
//{
//	Date a1;
//	Date a2(1, 1, 1);
//	a2 = a1;
//}

//循环链表
//#include<stdio.h>
//#include<string.h>
//#include<stdlib.h>
//
//
//
//typedef struct SListNode
//{
//    int _data;
//    struct SListNode* next;
//    struct SListNode* prev;
//}SL;
//
//SL* BuyNode(int data)
//{
//    SL* newNode = (SL*)malloc(sizeof(SL));
//    newNode->_data = data;
//    newNode->next = newNode;
//    newNode->prev = newNode;
//    return newNode;
//}
//
//void PushSL(SL** pnode, int data)
//{
//    SL* cur = *pnode;
//    SL* newnode = BuyNode(data);
//    if (*pnode == NULL)
//    {
//        *pnode = newnode;
//        return;
//    }
//    while (cur->next != *pnode)
//    {
//        cur = cur->next;
//    }
//    newnode->prev = cur;
//    newnode->next = cur->next;
//    cur->next = newnode;
//}
//
//void PopSL(SL* cur)
//{
//    cur->prev = cur->next;
//}
//
//int main()
//{
//    SL* p1 = NULL;
//    int n, m;
//    scanf(" %d %d", &n, &m);
//    int i;
//    for (i = 1; i <= n; i++)
//    {
//        PushSL(&p1, i);
//    }
//    int count = n;
//    i = 1;
//    SL* cur = p1;
//    while (count != 1)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cur = cur->next;
//        }
//        SL* next = cur->next;
//        PopSL(cur);
//        cur = next;
//        count--;
//    }
//    printf("%d", cur->_data);
//
//    return 0;
//}

////杭哥实现的自定义操作符“+”我对于（d1+4）那一块有疑惑
//using namespace std;
//class Date
//{
//public:
//	// 获取某年某月的天数
//	// 会频繁调用，所以直接放在类里面定义作为inline
//	int GetMonthDay(int year, int month)
//	{
//		static int days[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//		int day = days[month];
//		if (month == 2
//			&& ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)))
//		{
//			day += 1;
//		}
//
//		return day;
//	}
//
//	// 构造会频繁调用，所以直接放在类里面定义作为inline
//	Date(int year = 1, int month = 1, int day = 1)
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
//
//	void Print();
//
//
//	Date operator+(int day);
//	Date& operator+=(int day);
//
//
//
//
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//
//Date Date::operator+(int day)
//{
//	//Date ret(*this);
//	Date ret = *this;
//	ret += day;
//
//	return ret;
//}
//
//// d2 += d1 += 100
//Date& Date::operator+=(int day)
//{
//	_day += day;
//	while (_day > GetMonthDay(_year, _month))
//	{
//		_day -= GetMonthDay(_year, _month);
//		++_month;
//		if (_month == 13)
//		{
//			_year++;
//			_month = 1;
//		}
//	}
//
//	return *this;
//}
//void Date::Print()
//{
//	cout << _year << "/" << _month << "/" << _day << endl;
//}
//
//void TestDate2()
//{
//	Date d1(2022, 7, 24);
//	/*Date d2 = d1 + 4;
//	d2.Print();*/
//	(d1 + 4).Print();											//（当时此块有疑惑）
//	(d1 + 40).Print();// 跨月
//	(d1 + 400).Print();// 跨年
//	(d1 + 4000).Print(); // 跨闰年
//	(d1 + 40000).Print();
//}
//
//int main()
//{
//	TestDate2();
//
//	return 0;
//}

////日期类实现
////运算符重载
//using namespace std;
//class Date
//{
//public:
//	Date(int year=1, int month=1, int day=1)//构造函数
//	{
//		_year = year;
//		_month = month;
//		_day = day;
//	}
////此类不需要析构函数，没有需要析构的数据
////~Date(); 
//	Date(const Date& d)//拷贝构造函数
//	{
//		_year = d._year;
//		_month = d._month;
//		_day = d._day;
//	}
//
//	int GetMonthDay(int year, int month)
//	{
//		static int monthDay[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//		if (month == 2 && year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
//			return 29;
//		return monthDay[month];
//	}
//
//	int GetprevMonthDay(int year, int month)
//	{
//		month--;
//		if (month == 0)
//		{
//			month = 12;
//			year--;
//		}
//		static int monthDay[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//		if (month == 2 && year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
//			return 29;
//		return monthDay[month];
//	}
//
//	void Print();
//
//	Date operator + (const int day);
//
//	Date& operator += (const int day);
//
//	Date operator - (const int day);
//
//	Date& operator -= (const int day);
//
//	Date& operator ++();
//
//	Date operator ++(int);
//
//	Date& operator --();
//
//	Date operator --(int);
//
//	bool operator >(const Date& d);
//
//	bool operator >=(const Date& d);
//
//	bool operator <(const Date& d);
//
//	bool operator <=(const Date& d);
//
//	bool operator ==(const Date& d);
//
//
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//
//Date Date::operator + (const int day)
//{
//	Date ret = *this;
//	ret._day += day;
//	while (ret._day > GetMonthDay(ret._year, ret._month))
//	{
//		ret._day -= GetMonthDay(ret._year, ret._month);
//		ret._month++;
//		if (ret._month == 13)
//		{
//			ret._month = 1;
//			ret._year++;
//		}
//	}
//	return ret;
//}
//
//Date& Date::operator += (const int day)
//{
//	return *this = *this + day;
//}
//
//Date Date::operator - (const int day)
//{
//	Date ret = *this;
//	ret._day -= day;
//	while (ret._day<=0)
//	{
//		ret._day += GetprevMonthDay(ret._year, ret._month);
//		ret._month--;
//		if (ret._month == 0)
//		{
//			ret._month = 12;
//			ret._year--;
//		}
//	}
//	return ret;
//}
//
//Date& Date::operator -= (const int day)
//{
//	return *this = *this - day;
//}
//
//Date& Date::operator ++()
//{
//	return *this += 1;
//}
//
//Date Date::operator ++(int)
//{
//	Date ret = *this;
//	*this += 1;
//	return ret;
//}
//
//Date& Date::operator --()
//{
//	return *this -= 1;
//}
//
//Date Date::operator --(int)
//{
//	Date ret = *this;
//	*this -= 1;
//	return ret;
//}
//
//bool Date::operator >(const Date& d)
//{
//	return d._year < this->_year || 
//		d._year == this->_year && d._month < this->_month || 
//		d._year == this->_year && d._month == this->_month && d._day < this->_day;
//}
//
//bool Date::operator ==(const Date& d)
//{
//	return d._year == this->_year && d._month == this->_month && d._day == this->_day;
//}
//
//bool Date::operator >=(const Date& d)
//{
//	return *this > d || *this == d;
//}
//
//bool Date::operator <(const Date& d)
//{
//	return !(*this >= d);
//}
//
//bool Date::operator <=(const Date& d)
//{
//	return !(*this > d);
//}
//
//
//
//void Date::Print()
//{
//	cout << "你得到的日期是" << endl;
//	cout << _year << "年" << _month << "月" << _day << "日" << endl;
//}
//
//void Test()
//{
//	Date d1(2023, 5, 31);
//	Date d2=d1+1;
//	Date d3=d1-1;
//	Date d4=d1;
//	//(d1 - 40).Print();
//	//(d1 - 400).Print();
//	//(d1 - 4000).Print();
//	//d1.Print();
//	//(++d1).Print();
//	//(d1++).Print();
//	//d1.Print();
//	cout << (d2 > d1) << endl;
//	cout << (d3 < d1) << endl;
//	cout << (d3 == d1) << endl;
//	cout << (d2 >= d1) << endl;
//	cout << (d4 > d1) << endl;
//}
//
//int main()
//{
//	Test();
//	return 0;
//}
//
//typedef int DataType;
//class Stack
//{
//public:
//	Stack(size_t capacity = 10)
//	{
//		_array = (DataType*)malloc(capacity * sizeof(DataType));
//		if (nullptr == _array)
//		{
//			perror("malloc申请空间失败");
//			return;
//		}
//		_size = 0;
//		_capacity = capacity;
//	}
//	void Push(const DataType& data)
//	{
//		// CheckCapacity();
//		_array[_size] = data;
//		_size++;
//	}
//	//析构函数
//	~Stack()//这就是我们需要自己实现析构函数的情况（Stack）
//	{
//		if (_array)
//		{
//			free(_array);
//			_array = nullptr;
//			_capacity = 0;
//			_size = 0;
//		}
//	}
//
//	Stack operator =(const Stack& s);
//private:
//	DataType* _array;
//	size_t _size;
//	size_t _capacity;
//};
//
//int main()
//{
//	Stack s1;
//	s1.Push(1);
//	s1.Push(2);
//	s1.Push(3);
//	s1.Push(4);
//	Stack s2;
//	s2 = s1;
//	return 0;
//}

//int main()
//{
//	int i,j,k,n;
//	while (scanf("%d", &n) != EOF)
//	{
//		int count = 0;
//		for (i = 1; i < n; i++)
//			for (j = 1; j < i; j++)
//				for (k = 1; k < j; k++)
//					count++;
//		printf("%d %d", count,i+j+k);
//	}
//	return 0;
//}

////下面的代码说明了我们谁先声明就先初始化谁；
////我从调试发现我们好像是先定义了我们的的变量在进行初始化变量的；
//class A
//{
//public:
//	A(int a)
//		:_c(_a),
//		_a(a)
//	{
//	}
//	void Print()
//	{
//		cout << _a << endl<<_c;
//	}
//private:
//	int _a;
//	const int _c;
//	static int b;
//};
//
//int A::b = 0;
//int main()
//{
//	A a(1);
//	cout << sizeof(a);//证明了我们的类大小不包括这个静态变量；
//	return 0;
//}

//#include<stdio.h>
//int main()
//{
//	int a=1, b=1, c=2;
//	for (; c < 20000000;)
//	{
//		a = b;
//		b = c;
//		c = a + b;
//	}
//	printf("%d", b);
//	return 0;
//}

////日期相加
//#include <stdio.h>
//int GEtMonthDay(int y, int m)
//{
//    static int monthDay[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//    if ((m == 2) && (y % 4 == 0 && y % 100 != 0 || y % 400 == 0))
//    {
//        return 29;
//    }
//    return monthDay[m];
//}
//int main() {
//    int m, yr, mh, dy, d1;
//    scanf("%d", &m);
//    for (int i = 0; i < m; i++)
//    {
//        scanf(" %d%d%d%d", &yr, &mh, &dy, &d1);
//        dy += d1;
//        while (dy > GEtMonthDay(yr, mh))
//        {
//            dy -= GEtMonthDay(yr, mh);
//            mh++;
//            if (mh == 13)
//            {
//                mh = 1;
//                yr++;
//            }
//        }
//        printf("%04d-%02d-%02d\n", yr, mh, dy);
//    }
//    return 0;
//}

////打印日期
//#include <stdio.h>
//
//int GEtMonthDay(int y, int m)
//{
//    static int monthDay[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//    if ((m == 2) && (y % 4 == 0 && y % 100 != 0 || y % 400 == 0))
//    {
//        return 29;
//    }
//    return monthDay[m];
//}
//
//int main() {
//    int m, n;
//    while (scanf("%d%d", &m, &n) != EOF)
//    {
//        int y = m, mh = 1, d = n;
//        while (d > GEtMonthDay(y, mh))
//        {
//            d -= GEtMonthDay(y, mh);
//            mh++;
//            if (mh == 13)
//            {
//                mh = 1;
//                y++;
//            }
//        }
//        printf("%04d-%02d-%02d\n", y, mh, d);
//    }
//    return 0;
//}


//																			Josephus问题
//#include<stdio.h>
//#include<stdlib.h>
//
//
//typedef struct SLNode
//{
//    int _data;
//    struct SLNode* _next;
//    struct SLNode* _prev;
//}SL;
//SL* BuyNode(int data)
//{
//    SL* newnode = (SL*)malloc(sizeof(SL));
//    if (newnode == NULL)
//    {
//        printf("malloc fail\n");
//        exit(-1);
//    }
//    newnode->_data = data;
//    newnode->_next = newnode;
//    newnode->_prev = newnode;
//    return newnode;
//}
//void PushLsit(SL** pnode, int data)
//{
//    if (*pnode == NULL)
//    {
//        *pnode = BuyNode(data);
//    }
//    else {
//        SL* cur = *pnode;
//        SL* newnode = BuyNode(data);
//        newnode->_prev = cur->_prev;
//        newnode->_next = cur;
//        cur->_prev->_next = newnode;
//        cur->_prev = newnode;
//    }
//}
//void PopList(SL**node)
//{
//    SL*cur=*node;
//    SL* next = cur->_next;
//    cur->_prev->_next = cur->_next;
//    cur->_next->_prev = cur->_prev;
//    free(cur);
//    *node = next;
//}
//int main()
//{
//    SL* p1 = NULL;
//    int n;
//    while (scanf("%d", &n) != EOF)
//    {
//        for (int i = 1; i <= n; i++)
//        {
//            PushLsit(&p1, i);
//        }
//        SL* cur = p1;
//        int count = 1;
//        while (cur->_next != cur)
//        {
//            if (count == 2)
//            {
//                PopList(&cur);
//                count = 1;
//            }
//            else
//            {
//                count++;
//                cur = cur->_next;
//            }
//        }
//        printf("%d\n", cur->_data);
//        free(cur);
//        cur = NULL;
//        p1 = NULL;
//    }
//
//    return 0;
//}

//																	Josephus问题复杂版
//#include<stdio.h>
//#include<stdlib.h>
//#include<math.h>
//
//int main()
//{
//	int n;
//	while (scanf("%d", &n) != EOF)
//	{
//		int x = 1;
//		while ((pow(2, x) - 1) < n)
//		{
//			x++;
//		}
//		int m = pow(2, x - 1);
//		n -= (m - 1);
//		printf("%d\n", 2 * n - 1);
//	}
//	return 0;
//}


//																		真值表
//#include<stdio.h>
//#include<stdlib.h>
//#include<math.h>
//
//int main()
//{
//	char a[101] = { '\0' };
//	while (gets(a) != NULL)
//	{
//		int i = 0;
//		while (a[i] != '\0')
//		{
//			if (a[i] == '|' || a[i] == '-')
//			{
//				printf("%c%c ", a[i], a[i + 1]);
//				i += 2;
//			}
//			else if (a[i] == '<')
//			{
//				printf("%c%c%c ", a[i], a[i + 1], a[i + 2]);
//				i += 3;
//			}
//			else
//			{
//				if (a[i + 1] != '\0')
//					printf("%c ", a[i]);
//				else
//					printf("%c", a[i]);
//				i++;
//			}
//		}
//		printf("\n");
//		i = 0;
//		int count = 0;
//		while (a[i] != '\0')
//		{
//			if (a[i] >= 'a' && a[i] <= 'z')
//			{
//				count++;
//				if (a[i + 1] != '\0')
//					printf("%c ", a[i]);
//				else
//					printf("%c", a[i]);
//				i++;
//			}
//			else
//			{
//				i++;
//			}
//		}
//		printf("\n");
//		for (int j = 0; j < count; j++)
//		{
//			printf("")
//		}
//	}
//	return 0;
//}

//#include<stdio.h>
//int main()
//{
//	int b = 1;
//	int* a = &b;
//	printf("%d", sizeof(a));
//}

////											栈的实现
//typedef int DataType;
//
//typedef struct Stack
//{
//	DataType* _data;
//	int top;
//	int capcity;
// }S;
//
//void InitStack(S*s)//初始化栈；
//{
//	s->capcity = 100;
//	s->_data = malloc(sizeof(DataType) * s->capcity);
//	s->top = 0;
//}
//
//int main()
//{
//	S p1;
//	InitStack(&p1);
//	return 0;
//}

////															进度条代码
//#include<iostream>
//#include<windows.h>
//
//using namespace std;
//int main()
//{
//	char percent[102]={0};
//	char buffer[5] = "-\|//";
//	fflush(stdout);
//	for (int i = 0; i <= 100; i++)
//	{
//		printf("[%-100s][%%%d] %c\r", percent, i,buffer[i%4]);
//		fflush(stdout);
//		percent[i] = '#';
//		Sleep(5);
//	}
//	
//
//	//通过刚刚的测试你也看到了，现象没有问题，我们控制台本身的文本信息是有一个空行的，所以换行
//	//打印的时候是出现了一个空行，这跟代码没关系，是控制台的设定
//
//
//	//printf("hello world\r");
//	//fflush(stdout);
//	//Sleep(1000);
//
//	return 0;
//}


//									日期相减
//#include <stdio.h>
//#include<math.h>
//
//int GetMonthDay(int m, int y)
//{
//    int month[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//    if ((m == 2) && (y % 4 == 0 && y % 100 != 0 || y % 400 == 0))
//    {
//        return 29;
//    }
//    return month[m];
//}
//
//int GetYearDay(int y)
//{
//    if (y % 4 == 0 && y % 100 != 0 || y % 400 == 0)
//    {
//        return 366;
//    }
//    else {
//        return 365;
//    }
//}
//
//int main() {
//    int y, y1, m1, m, d1, d;
//    scanf("%4d%2d%2d", &y, &m, &d);
//    scanf("%4d%2d%2d", &y1, &m1, &d1);
//    int n = 0, n1 = 0;
//    int tmp = y;
//    while (tmp >= 0)
//    {
//        tmp--;
//        n += GetYearDay(tmp);
//    }
//    while (--m > 0)
//    {
//        n += GetMonthDay(m, y);
//    }
//    n += d;
//
//
//    tmp = y1;
//    while (tmp >= 0)
//    {
//        tmp--;
//        n1 += GetYearDay(tmp);
//    }
//    while (--m1 > 0)
//    {
//        n1 += GetMonthDay(m1, y1);
//    }
//    n1 += d1;
//    printf("%d", abs(n - n1)+1);
//    return 0;
//}

////															计算日期所处时间
//#include <iostream>
//using namespace std;
//
//int GetMonthDay(int m, int y) {
//    int month[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//    if ((m == 2) && (y % 4 == 0 && y % 100 != 0 || y % 400 == 0)) {
//        return 29;
//    }
//    return month[m];
//}
//
//int main() {
//    int y,m,d;
//    scanf("%d%d%d", &y, &m, &d);
//    int n=0;
//    while(--m)
//    {
//        n+=GetMonthDay(m, y);
//    }
//    n+=d;
//    printf("%d",n);
//    return 0;
//}
////														输出字符串中的数字字符
//#include <stdio.h>
//#include<string.h>
//#include<stdlib.h>
//
//int main() {
//    char str[256];
//    int num = 0;
//    gets(str);
//    int i = 0, max = 0, j = 0, maxi = 0, k = 0;
//    while (str[i] != '\0')
//    {
//        while (str[i] >= '0' && str[i] <= '9')
//        {
//            j = 1, k = i;
//            while (str[i + 1] >= '0' && str[i + 1] <= '9' && str[i + 1] != '\0')
//            {
//                j++;
//                i++;
//            }
//            if (j > max)
//            {
//                max = j;
//                maxi = k;
//            }
//            i++;
//        }
//        if (str[i] == '\0')
//        {
//            break;
//        }
//        else {
//            i++;
//        }
//    }
//    str[maxi + max] = '\0';
//    printf("%s", str + maxi);
//    return 0;
//}

//											数组复制
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	/*char a[10] = "123456";
//	char b[] = "\0";
//	strcpy(a + 4, b);
//	return 0;*/
//	char dog[] = "wang\0miao";
//}

////                                                      回文数组问题
//#include <stdio.h>
//#include<stdbool.h>
//#include<string.h>
//bool invert(char* str, int size)
//{
//    int left = 0, right = size - 1, judge = 1;
//    while (left++ < right--)
//    {
//        if (str[left] != str[right])
//        {
//            judge = 0;
//            return false;
//        }
//    }
//    return true;
//}
//
//int main() {
//    char a[101] = { 0 }, b[101] = { 0 }, c[201] = { 0 };
//    scanf("%s %s", a, b);
//    int sizea = 0, sizeb = 0;
//    sizea = strlen(a);
//    sizeb = strlen(b);
//    int n = 0;
//    for (int i = 0; i <= sizea; i++)
//    {
//        memset(c, 0, sizeof(c));
//        strcpy(c, a);
//        strcpy(c + i, b);
//        strcpy(c + i + sizeb, a + i);
//        if (invert(c, strlen(c)) == true)
//        {
//            n++;
//        }
//    }
//    printf("%d", n);
//    return 0;
//}

////                                                              找到第一个没有重复出现的字符
//class Solution {
//public:
//    int firstUniqChar(string s) {
//        int num[26] = { 0 };
//        for (int i = 0; i < s.size(); i++)
//        {
//            num[s[i] - 'a']++;
//        }
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (num[s[i] - 'a'] == 1)
//            {
//                return i;
//            }
//        }
//        return -1;
//    }
//};

//														字符串最后一个单词的长度
//#include <iostream>
//using namespace std;
//int main() {
//	string s;
//	getline(cin, s);
//	int n = s.rfind(' ');
//	cout << s.size() - n - 1;
//}

////																  验证回文串
//class Solution {
//public:
//    bool isPalindrome(string s) {
//        for (auto& ch : s)
//        {
//            if (ch >= 'A' && ch <= 'Z')
//            {
//                ch += 32;
//            }
//        }
//        int left = 0, right = s.size() - 1;
//        while (left < right)
//        {
//            if (s[left] >= 'a' && s[left] <= 'z' || s[left] >= '0' && s[left] <= '9')
//            {
//                if (s[right] >= 'a' && s[right] <= 'z' || s[right] >= '0' && s[right] <= '9')
//                {
//                    if (s[left++] != s[right--])
//                    {
//                        return false;
//                    }
//                }
//                else {
//                    right--;
//                }
//            }
//            else
//            {
//                left++;
//            }
//        }
//        return true;
//    }
//};

////                                                              两个大数相加
//#include<iostream>
//#include<string>
//using namespace std;
//class Solution {
//public:
//    string addStrings(string num1, string num2) {
//        string num;
//        int carry = 0, i = 0;
//        while (num1.size() > i || num2.size() > i)
//        {
//            int tmp = 0;
//            if (num1.size() > i && num2.size() > i)
//            {
//                tmp = num1[num1.size() - 1 - i] - '0' + num2[num2.size() - 1 - i] - '0' + carry;
//            }
//            else if (num1.size() > i && num2.size() <= i)
//            {
//                tmp = num1[num1.size() - 1 - i] - '0' + carry;
//            }
//            else if (num2.size() > i && num1.size() <= i)
//            {
//                tmp = num2[num2.size() - 1 - i] - '0' + carry;
//            }
//            if (tmp > 9)
//            {
//                carry = 1;
//                tmp = tmp % 10;
//            }
//            else {
//                carry = 0;
//            }
//            char a = tmp + '0';
//            num += a;
//            i++;
//        }
//        if (carry == 1)
//        {
//            num += '1';
//        }
//        reverse(num.begin(), num.end());
//        return num;
//    }
//};
//int main()
//{
//    Solution s;
//    string num1("9");
//    string num2("99");
//    cout<< s.addStrings(num1, num2);
//    return 0;
//}

////                                                              将字符串转换为整形数字
//#include<math.h>
//class Solution {
//public:
//    int StrToInt(string str) {
//        int i = 0;
//        int numsize = 0;
//        string num;
//        num.reserve(20);
//        int sign = 1;
//        if (str[0] == '+')
//        {
//            sign = 1;
//            i++;
//        }
//        if (str[0] == '-')
//        {
//            sign = -1;
//            i++;
//        }
//        while (i < str.size())
//        {
//            if (!(str[i] >= '0' && str[i] <= '9'))
//            {
//                return 0;
//            }
//            num += str[i++];
//            numsize++;
//        }
//        reverse(num.begin(), num.end());
//        int sum = 0;
//        for (int j = 0; j < numsize; j++)
//        {
//            int tmp = num[j] - '0';
//            sum += tmp * pow(10, j);
//        }
//        return sum*sign;
//    }
//};
//int main()
//{
//    string str("+2147483647");
//    Solution s;
//    cout<<s.StrToInt(str);
//    return 0;
//}

////														寻找最接近的斐波那契数
//#include <iostream>
//using namespace std;
//int main() {
//    int prev = 0, next = 1;
//    int n;
//    cin >> n;
//    if (n == 0 || n == 1) {
//        cout << "0";
//    }
//    else{
//        while (n > prev + next)
//        {
//            int tmp = prev + next;
//            prev = next;
//            next = tmp;
//        }
//        int mindel = n - next;
//        int maxdel = next + prev - n;
//        maxdel > mindel ? cout << mindel : cout << maxdel;
//    }
//    return 0;
//}

////                                                                正确括号问题
//typedef char* DataType;
//typedef struct Stack
//{
//    int _size;
//    int _capacity;
//    DataType _data;
//}S;
//void InitStack(S* s1, int size)
//{
//    s1->_size = 0;
//    s1->_capacity = size;
//    s1->_data = new char[size];
//}
//void PushStack(S* s1, char data)
//{
//    s1->_data[s1->_size++] = data;
//}
//void PopStack(S* s1)
//{
//    s1->_size--;
//}
//class Parenthesis {
//public:
//    bool chkParenthesis(string A, int n) {
//        S s;
//        InitStack(&s, A.size());
//        int i = 0;
//        cout << A << n;
//        for (auto ch : A)
//        {
//            if (ch == '(')
//            {
//                PushStack(&s, ch);
//            }
//            else if (ch == ')')
//            {
//                if (s._size == 0)
//                {
//                    return false;
//                }
//                PopStack(&s);
//            }
//            else
//            {
//                return false;
//            }
//        }
//        return true;
//    }
//};
//int main()
//{
//	Parenthesis a;
//	string b("()()a()()");
//    cout << a.chkParenthesis(b, b.size());
//
//	return 0;
//}

////	                                                    找最大公倍数														
//#include <stdio.h>
//int main() {
//    int a, b;
//    cin >> a>>b;
//    int max, min;
//    a > b ? max = a, min = b : max = b, min = a;
//    int remainder = max % min;
//    while (remainder != 0) {
//        max = min;
//        min = remainder;
//        remainder = max % min;
//    }
//    int answer = a * b / min;
//    printf("%d", answer);
//    return 0;
//}

////															不使用+号等算数运算符进行+运算
//class UnusualAdd {
//public:
//	int addAB(int A, int B) {
//		if (A == 0)return B;
//		if (B == 0)return A;
//		int a = A ^ B;//本位数据
//		int b = (A & B) << 1;//进位数据
//		return addAB(a, b);
//	}
//};

////																计算在m*n的方格中从左上到右下的可移动方式
//#include <iostream>
//using namespace std;
//int add(int m, int n)
//{
//    if (m == 0 || n == 0)
//    {
//        return 0;
//    }
//    else if (m > 1 && n > 1)
//    {
//        return add(m - 1, n) + add(m, n - 1);
//    }
//    else {//肯定是要么m==1||n==1这两种情况进入这个else
//        return m + n;
//    }
//}
//int main() {
//    int m, n;
//    cin >> m >> n;
//    cout << add(m, n);
//}

////                                                              密码的强度检查
//#include <iostream>
//#include<string>
//using namespace std;
//void WdLen(string& password, int* gred) {
//    if (password.size() <= 4) {
//        *gred += 5;
//    }
//    else if (password.size() >= 5 && password.size() <= 7) {
//        *gred += 10;
//    }
//    else {
//        *gred += 25;
//    }
//}
//void alph(string& p, int* gred) {
//    int judge = 0;
//    int bigword = 0, smallword = 0, num = 0, sign = 0;
//    for (int i = 0; i < p.size(); i++) { //找出大小写字符
//        if (p[i] >= 'A' && p[i] <= 'Z' || p[i] >= 'a' && p[i] <= 'z') {
//            *gred += 10;
//            if (p[i] >= 'A' && p[i] <= 'Z') {
//                judge = 2;//大写
//                bigword = 1;
//            }
//            else {
//                judge = 1;//小写
//                smallword = 1;
//            }
//            i++;
//            while (i < p.size()) {
//                if (p[i] >= 'a' && p[i] <= 'z' && judge == 2) { //有过大写字符了
//                    *gred += 10;
//                    smallword = 1;
//                    break;
//                }
//                if (p[i] >= 'A' && p[i] <= 'Z' && judge == 1) { //有过小写字符了
//                    *gred += 10;
//                    bigword = 1;
//                    break;
//                }
//                i++;
//            }
//            break;
//        }
//    }
//    judge = 0;
//    for (int i = 0; i < p.size(); i++) { //找出数字字符
//        if (p[i] >= '0' && p[i] <= '9') {
//            num = 1;
//            if (judge == 1) {
//                *gred += 10;
//                break;
//            }
//            *gred += 10;
//            judge = 1;
//        }
//    }
//    judge = 0;
//    for (int i = 0; i < p.size(); i++) { //找出符号字符
//        if (!(p[i] >= '0' && p[i] <= '9' || p[i] >= 'A' && p[i] <= 'Z' || p[i] >= 'a' &&
//            p[i] <= 'z')) {
//            sign = 1;
//            if (judge == 1) {
//                *gred += 15;
//                break;
//            }
//            *gred += 10;
//            judge = 1;
//        }
//    }
//    if (sign == 1 && num == 1 && bigword == 1 && smallword == 1) {
//        *gred += 5;
//    }
//    else if (sign == 1 && num == 1 && bigword == 1 || sign == 1 && num == 1 &&
//        smallword == 1) {
//        *gred += 3;
//    }
//    else if (num == 1 && bigword == 1 || num == 1 && smallword == 1) {
//        *gred += 2;
//    }
//}
//int main() {
//    string password;
//    getline(cin, password);
//    int gred = 0;
//    WdLen(password, &gred);//检查符号并打分
//    alph(password, &gred);
//    if (gred >= 0 && gred < 25) {
//        printf("VERY_WEAK");
//    }
//    else if (gred >= 25 && gred < 50) {
//        printf("WEAK");
//    }
//    else if (gred >= 50 && gred < 60) {
//        printf("AVERAGE");
//    }
//    else if (gred >= 60 && gred < 70) {
//        printf("STRONG");
//    }
//    else if (gred >= 70 && gred < 80) {
//        printf("VERY_STRONG");
//    }
//    else if (gred >= 80 && gred < 90) {
//        printf("SECURE");
//    }
//    else if (gred >= 90) {
//        printf("VERY_SECURE");
//    }
//}

////													这个代码我们可以看到编译器对常量的替换
//#include <iostream>
//using namespace std;
//int main(void)
//{
//	const int a = 10;
//	int* p = (int*)(&a);
//	*p = 20;
//	cout << "*p = " << *p << ",a = " << a << endl; 
//	printf("&a%p\np%p", &a, p);//地址相同果然是常替换
//	return 0;////最后我们可以发现调试中我们的a被改
//			////变了但是我们最后的结果还是10所以证明了我们a在被输出时是发生了替换的
//}

////											证明我们的赋值运算符只能写为成员函数2023.10.13
//class Data
//{
//public:
//	explicit Data(int n=0)
//		:_time(n)
//	{}
//	friend Data& operator =(Data& a, const Data& b);
//	/*Data& operator =(const Data& b)
//	{
//		this->_time = b._time;
//		return *this;
//	}*/
//private:
//	int _time;
//};
//Data& operator =(Data &a,const Data& b)//这样的写法没有语法错误但是就是不能这么写
//	{
//		a._time = b._time;
//		return a;
//	}
//int main()
//{
//	Data a(5);
//	Data b = Data(5);
//	return 0;
//}

////													找到两个节点的最近的祖先节点
//class LCA {//这题有点坑刚刚好卡在3ms门槛上
//public:
//	int getLCA(int a, int b) {
//		while (a != b)
//		{
//			if (a > b)
//				a /= 2;
//			else
//				b /= 2;
//		}
//		return a;
//	}
//};

////												求最大的连续bit位的数
//#include <iostream>
//using namespace std;
//int main() {
//    int a;
//    cin >> a;
//    string num;
//    int max = 0, count = 0;
//    for (int i = 0; i < 32; i++)
//    {
//        num += (((a >> i) & 1) + '0');
//    }
//    for (int i = 0; i < 32; i++)
//    {
//        count = 0;
//        while (num[i] == '1')
//        {
//            if (num[i] == '1')
//            {
//                count++;
//                if (max < count)
//                {
//                    max = count;
//                }
//            }
//            i++;
//        }
//    }
//    cout << max;
//}

////															找一个偶数的两个最近的素数相加2023.10.14
//#include <cmath>
//#include <iostream>
//using namespace std;
//#include<stdbool.h>
//#include<math.h>
//
//bool Isprime(int n) {
//    for (int i = 2; i <= n / 2; i++) {
//        for (int j = 2; j <= sqrt(n); j++) {
//            if ((i * j) == n) {
//                return true;
//                break;
//            }
//        }
//    }
//    return false;
//}
//void Judge(int n, int m) {
//    for (int i = m; i > 1; i--) {
//        if (Isprime(i) == false) {
//            for (int j = m; j < n; j++) {
//                if (Isprime(j) == false) {
//                    if (i + j == n) {
//                        cout << i << endl << j;
//                        return;
//                    }
//                }
//            }
//        }
//    }
//}
//int main() {
//    int n;
//    cin >> n;
//    int m = n / 2;
//    Judge(n, m);
//}

////														插入二进制数
//class BinInsert {
//public:
//	int binInsert(int n, int m, int j, int i) {
//		n = (m << j) | n;
//		return n;
//	}
//};

////															 两个大数相乘
//class Solution {
//public:
//    string multiply(string num1, string num2) {
//        if (num1.size() == 1 && num1[0] == '0' || num2.size() == 1 && num2[0] == '0')
//        {
//            string x("0");
//            return x;
//        }
//        int carry = 0;
//        int n1 = num1.size() - 1;
//        int n2 = num2.size() - 1;
//        int count = 0;
//        string num;
//        string sum;//乘每位获得的数
//        string prevsum;//前一位相乘每位获得的数
//        for (int i = n1; i >= 0; i--)
//        {
//            int tmp = 0;
//            for (int j = n2; j >= 0; j--)
//            {
//                tmp = (num1[i] - '0') * (num2[j] - '0') + carry;
//                if (tmp > 9)
//                {
//                    carry = tmp / 10;
//                    tmp %= 10;
//                }
//                else
//                {
//                    carry = 0;
//                }
//                sum += tmp + '0';
//            }
//            if (carry != 0)
//            {
//                sum += carry + '0';
//                carry = 0;
//            }
//            reverse(sum.begin(), sum.end());
//            int s = sum.size() - 1;
//            int p = prevsum.size() - 1;
//            if (p == -1)
//            {
//                prevsum = sum;
//            }
//            else {
//                count++;
//                for (int k = 0; k < count; k++)
//                {
//                    sum += '0';
//                }
//                s += count;
//                while (p >= 0 || s >= 0)
//                {
//                    if (p >= 0 && s >= 0)
//                    {
//                        tmp = (prevsum[p--] - '0') + (sum[s--] - '0') + carry;
//                    }
//                    else if (s >= 0 && p < 0)
//                    {
//                        tmp = sum[s--] - '0' + carry;
//                    }
//                    else {
//                        tmp = prevsum[p--] - '0' + carry;
//                    }
//                    if (tmp > 9)
//                    {
//                        carry = tmp / 10;
//                        tmp %= 10;
//                    }
//                    else
//                    {
//                        carry = 0;
//                    }
//                    num += tmp + '0';
//                }
//                if (carry != 0)
//                {
//                    num += carry + '0';
//                    carry = 0;
//                }
//                reverse(num.begin(), num.end());
//                prevsum.clear();
//                prevsum = num;
//                num.clear();
//            }
//            sum.clear();
//        }
//        return prevsum;
//    }
//};
//
//int main()
//{
//    Solution a;
//    string m("123");
//    string n("456");
//    a.multiply(m, n);
//    return 0;
//}

////																	两大数相乘复盘
////1.需要注意我们的tmp要先赋值给我们的carry再去模等
////2.需要注意我们的数每次乘完另一个数之后我们要考虑进位再后面加0
////3.要考虑特殊情况，当我们的一个数为0时的情况
////4.循环时的递归需要注意不要漏掉了
////5.字符串相加后一定是需要反转的
//class Solution {
//public:
//	string multiply(string num1, string num2) {
//		if (num1.size() == 1 && num1[0] == '0' || num2.size() == 1 && num2[0] == '0')
//		{
//			string x("0");
//			return x;
//		}
//		string num;//乘完后相加的位置
//		string sum;//相乘后放的位置
//		string prevsum;//上一次相乘的数据放的位置
//		int count = 0;//记录加的次数让我们每次加法进位 
//		for (int i = num1.size() - 1; i >= 0; i--)//先做乘法
//		{
//			int carry = 0;//进位
//			int data = 0;//每一位的数据
//			for (int j = num2.size() - 1; j >= 0; j--)
//			{
//				data = (num1[i] - '0') * (num2[j] - '0')+carry;
//				if (data > 9)
//				{
//					carry = data / 10;
//					data %= 10;
//				}
//				else
//				{
//					carry = 0;
//				}
//				sum += data+'0';
//			}
//			if (carry != 0)
//			{
//				sum += carry+'0';
//				carry = 0;//重置一下
//			}
//			reverse(sum.begin(), sum.end());
//			//乘法做完一个数之后将这个数的数据和已经得到了的数据相加——做加法
//			if (prevsum.size() == 0)//如果是第一次就得先赋值
//			{
//				prevsum = sum;
//			}
//			else
//			{
//				count++;
//				for (int k = 0; k < count; k++)
//				{
//					sum += '0';
//				}
//				int s = sum.size() - 1;
//				int p = prevsum.size() - 1;
//				while (s >= 0 || p >= 0)
//				{
//					int x = s >= 0 ? (sum[s--] - '0'): 0;
//					int y = p >= 0 ? (prevsum[p--] - '0'): 0;
//					data = x + y+carry;
//					if (data > 9)
//					{
//						carry = data / 10;
//						data %= 10;
//					}
//					else
//					{
//						carry = 0;
//					}
//					num += data+'0';
//				}
//				if (carry != 0)
//				{
//					num += carry + '0';
//					carry = 0;
//					data = 0;
//				}
//				reverse(num.begin(), num.end());
//				prevsum.clear();
//				prevsum = num;
//				num.clear();
//			}
//			sum.clear();
//		}
//		return prevsum;
//	}
//};
//int main()
//{
//	string m("123");
//	string n("456");
//	Solution a;
//	cout<<a.multiply(m, n);
//	return 0;
//}

////                                                          反转字符中的单词
//class Solution {
//public:
	//void reverse(string& s, int left, int right)
	//{
	//    while (left < right)
	//    {
	//        char tmp = s[left];
	//        s[left] = s[right];
	//        s[right] = tmp;
	//        left++;
	//        right--;
	//    }
//    }
//    string reverseWords(string s) {
//        int first = 0;
//        int space = s.find(' ', first);
//        while(space!=-1)
//        {
//            reverse(s, first, space - 1);
//            first = space + 1;
//            space = s.find(' ', first);
//        }
//        space = s.size();
//        reverse(s, first, space - 1);
//        return s;
//    }
//};
//int main()
//{
//    string s("Let's take LeetCode contest");
//    Solution a;
//    cout<<a.reverseWords(s);
//    return 0;
//}

////                                                      反转字符串中的部分字符
//class Solution {
//public:
//    void reverse(string& s, int left, int right)
//    {
//        while (left < right)
//        {
//            char tmp = s[left];
//            s[left] = s[right];
//            s[right] = tmp;
//            left++;
//            right--;
//        }
//    }
//    string reverseStr(string s, int k) {
//        for (int i = 0; i < s.size(); i += 2 * k)
//        {
//            if (i + k > s.size())
//            {
//                reverse(s, i, s.size() - 1);
//                return s;
//            }
//            reverse(s, i, i + k - 1);
//        }
//        return s;
//    }
//};

////                                                              参数分析2023.10.16
// //1.本题我们需要注意“”双引号的作用只是为了让我们知道它里面包含的是字符串，起到的是旗帜的作用我们不能用它来当作换行符
// //2.真正需要换行的时候是我们遇见字符串外面的空格的时候
//#include <iostream>
//using namespace std;
//int main() {
//    string n;
//    getline(cin, n);
//    int count = 1;
//    for (int i = 0; i < n.size(); i++)
//    {
//        if (n[i] == '"')
//        {
//            i++;
//            while (n[i] != '"')
//            {
//                i++;
//            }
//        }
//        else if (n[i] == ' ')
//        {
//            count++;
//        }
//    }
//    cout << count << endl;
//    for (int i = 0; i < n.size(); i++)
//    {
//        if (n[i] == '"')
//        {
//            i++;
//            while (n[i] != '"')
//            {
//                cout << n[i];
//                i++;
//            }
//        }
//        else if (n[i] == ' ')
//        {
//            cout << endl;
//        }
//        else {
//            cout << n[i];
//        }
//    }
//}
////比特方法使用顺序表来放数据
//#include <iostream>
//#include <vector>
//using namespace std;
//int main() {
//    string n;
//    getline(cin, n);
//    vector<string>s;
//    int count = 0;
//    string tmp;
//    for (int i = 0; i < n.size(); i++)
//    {
//        if (n[i] == '"')
//        {
//            i++;
//            while (n[i] != '"')
//            {
//                tmp+=n[i++];
//            }
//        }
//        else if (n[i] == ' ')
//        {
//            s.push_back(tmp);
//            tmp.clear();
//            count++;
//        }
//        else {
//            tmp += n[i];
//        }
//    }
//    s.push_back(tmp);
//    cout << count + 1 << endl;
//    for (int i = 0; i < s.size(); i++)
//    {
//        cout << s[i] << endl;
//    }
//}
////自己的改进代码
// //我们对string加入数据时我们的vector没有改变，所以我们得先改变vector不然它无法增长
//#include <iostream>
//#include <vector>
//using namespace std;
//int main() {
//    string n;
//    getline(cin, n);
//    vector<string>s;
//    s.push_back("");
//    int count = 0;
//    for (int i = 0; i < n.size(); i++)
//    {
//        if (n[i] == '"')
//        {
//            i++;
//            while (n[i] != '"')
//            {
//                s[count].push_back(n[i++]);
//            }
//        }
//        else if (n[i] == ' ')
//        {
//            count++;
//            s.push_back("");
//        }
//        else {
//            s[count].push_back(n[i]);
//        }
//    }
//    cout << count + 1 << endl;
//    for (int i = 0; i < s.size(); i++)
//    {
//        cout << s[i] << endl;
//    }
//}
// 
////                                                    跳石板问题（动态规划）
//#include<iostream>
//using namespace std;
//#include<vector>
//#include<math.h>
//void GetDiv(vector<int>& div, int n)
//{
//    for (int i = 2; i <= sqrt(n); i++)
//    {
//        if (n % i == 0)
//        {
//            div.push_back(i);
//            if ((n / i) != i)
//            {
//                div.push_back((n / i));
//            }
//        }
//    }
//}
//int GetLittleStep(int n, int m)
//{
//    vector<int> a(m + 1, -1);
//    a[n] = 0;
//    for (int i = n; i < m; i++)
//    {
//        if (a[i] != -1)
//        {
//            vector<int>div;
//            GetDiv(div,i);
//            for (int j = 0; j < div.size(); j++)
//            {
//                if (div[j] + i > m)
//                {
//                    continue;
//                }
//                if (a[i + div[j]] == -1)
//                {
//                    a[i + div[j]] = a[i] + 1;
//                }
//                else
//                {
//                    a[i + div[j]] = a[i + div[j]] < a[i] + 1 ? a[i + div[j]] : a[i] + 1;
//                }
//            }
//        }
//    }
//    return a[m];
//}
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    cout << GetLittleStep(n, m);
//    return 0;
//}

////                                                                       电话号码的数字组合（递归问题）
//#include<iostream>
//using namespace std;
//#include<vector>
//#include<math.h>
//class Solution {
//    string letter[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
//public:
//    void GetStr(vector<string>& str, int f, string comstr, string& digits)
//    {
//        if (f == digits.size())
//        {
//            str.push_back(comstr);
//            return;
//        }
//        int n = digits[f] - '0';
//        for (int i = 0; i < letter[n].size(); i++)
//        {
//            char ch = letter[n][i];
//            GetStr(str, f + 1, comstr + ch, digits);
//        }
//    }
//    vector<string> letterCombinations(string digits) {
//        vector<string>str;
//        string tmpstr;
//        if (digits.size() == 0)
//        {
//            return str;
//        }
//        GetStr(str, 0, tmpstr, digits);
//        return str;
//    }
//};
//int main()
//{
//    Solution a;
//    a.letterCombinations(string("23"));
//    return 0;
//}

////                                                          计算日期所在天数2023.10.17
//#include <iostream>
//using namespace std;
//int GetMothDay(int year, int month)
//{
//    int monthDay[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//    if (month == 2 && year % 4 == 0 && year % 100 != 0 || month == 2 && year % 400 == 0)
//    {
//        return 29;
//    }
//    return monthDay[month];
//}
//int main() {
//    int year, month, day;
//    cin >> year >> month >> day;
//    int sum = 0;
//    for (int i = 0; i < month; i++)
//    {
//        sum += GetMothDay(year, i);
//    }
//    sum += day;
//    cout << sum;
//}

////                                                          直接查找二进制数中1的个数2023.10.18
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    while (cin >> n)
//    {
//        int count = 0;
//        for (int i = 0; i < 32; i++)
//        {
//            int tmp = (n >> i) & 1;
//            if (tmp == 1)
//            {
//                count++;
//            }
//        }
//        cout << count << endl;
//    }
//}

////                                                              求拿手套的最小个数
//#include<limits.h>
//class Gloves {
//public:
//    int CountNum(int n, vector<int>& left, vector<int>& right)
//    {
//        int suml = 0, sumr = 0, minl = INT_MAX, minr = INT_MAX;
//        int sum = 0;
//        for (int i = 0; i < left.size(); i++)
//        {
//            if (left[i] == 0 || right[i] == 0)
//            {
//                sum += left[i] + right[i];
//            }
//            else {
//                suml += left[i];
//                minl = left[i] < minl ? left[i] : minl;
//                sumr += right[i];
//                minr = right[i] < minr ? right[i] : minr;
//            }
//        }
//        int min = suml - minl > sumr - minr ? sumr - minr : suml - minl;
//        return sum + min + 1 + 1;
//    }
//    int findMinimum(int n, vector<int> left, vector<int> right) {
//        int count = CountNum(n, left, right);
//        return count;
//    }
//};

////                                                              完全数计算2023.10.19
//#include <iostream>
//#include<math.h>
//using namespace std;
//int GetNum(int n)
//{
//    int sum = 0;
//    for (int i = 2; i <= sqrt(n); i++)
//    {
//        if (n % i == 0)
//        {
//            sum += i;
//            if (i != n / i)
//            {
//                sum += n / i;
//            }
//        }
//    }
//    if (n == 1)
//    {
//        return 0;
//    }
//    if (sum + 1 == n)
//    {
//        return 1;
//    }
//    return 0;
//}
//int main() {
//    int n;
//    cin >> n;
//    int count = 0;
//    for (int i = 0; i < n; i++)
//    {
//        count += GetNum(i);
//    }
//    cout << count;
//    return 0;
//}

////                                                  扑克牌大小问题2023.10.20
//#include <iostream>
//#include<vector>
//#include<string>
//using namespace std;
//void JudgeJk(string m) {
//    size_t pos =
//        m.find("joker JOKER");//如果有王炸直接输出，其实这是最意外的条件应该是最后再考虑的；（最以外的条件最后考虑）
//    if (pos != -1) {
//        cout << "joker JOKER";
//        return;
//    }
//    pos = m.find('-');//分开字符串
//    string str1 = m.substr(0, pos);
//    string str2 = m.substr(pos + 1, m.size());
//    int count1 = 1, count2 = 1;
//    pos = str1.find(' ');
//    while (pos != -1) {
//        pos = str1.find(' ', pos + 1);
//        count1++;
//    }
//    pos = str2.find(' ');
//    while (pos != -1) {
//        pos = str2.find(' ', pos + 1);
//        count2++;
//    }
//    if (count1 != count2) { //当类型不同时
//        if (count1 == 4 || count2 == 4) {
//            cout << (count1 == 4 ? str1 : str2);
//            return;
//        }
//        else {
//            cout << "ERROR";
//            return;
//        }
//    }
//    else {
//        string word = "3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER";
//        string word1 = str1.substr(0, str1.find(' '));
//        string word2 = str2.substr(0, str2.find(' '));
//        int pos1, pos2;
//        pos1 = word.find(word1);
//        pos2 = word.find(word2);
//        cout << (pos1 > pos2 ? str1 : str2);
//    }
//}
//int main() {
//    vector<string>n;
//    string m;
//    char tmp;
//    getline(cin, m);
//    JudgeJk(m);
//}

//                                                    变形杨辉三角问题2023.10.23
//#include <iostream>
//#include<vector>
//using namespace std;
//int main() {
//    int n;
//    cin >> n;
//    vector<int> m(2 * n - 1, 0);
//    vector<vector<int>> v(n, m);
//    int judge = 0;
//    v[0][0] = 1;
//    for (int i = 1; i < n; i++)
//    {
//        v[i][0] = v[i][2 * i] = 1;
//        for (int j = 1; j < 2 * i; j++)
//        {
//            if (j == 1)
//            {
//                v[i][j] = v[i - 1][j - 1] + v[i - 1][j];
//            }
//            else {
//                v[i][j] = v[i - 1][j - 2] + v[i - 1][j - 1] + v[i - 1][j];
//            }
//            if (i == n - 1)
//            {
//                if (0 == v[i][j] % 2)
//                {
//                    cout << j + 1;
//                    judge = 1;
//                    break;
//                }
//            }
//        }
//    }
//    if (judge == 0)
//        cout << -1;
//    return 0;
//}
//#include <iostream>//找规律优化后
//#include<vector>
//using namespace std;
//int main() {
//    int n;
//    cin >> n;
//    int num[4] = { 4,2,3,2 };
//    int answer = -1;
//    if (n > 2)
//        answer = num[(n - 2) % 4];
//    cout << answer;
//}

////                                                      字符串中的字符出现次数
//#include <iostream>
//using namespace std;
//int main() {
//    string n;
//    getline(cin, n);
//    char ch;
//    cin >> ch;
//    if (ch >= 'a' && ch <= 'z')
//    {
//        ch -= 32;
//    }
//    int count = 0;
//    for (int i = 0; i < n.size(); i++)
//    {
//        if (n[i] >= 'a' && n[i] <= 'z')
//        {
//            n[i] -= 32;
//        }
//        if (ch == n[i])
//            count++;
//    }
//    cout << count;
//}

////                                                  斐波那契数
//#include <iostream>
//using namespace std;
//int main() {
//    int m, count = 0;
//    cin >> m;
//    if (m < 3)
//    {
//        count = 1;
//    }
//    else {
//        int a = 1, b = 1;
//        while (m > 2)
//        {
//            count = a + b;
//            a = b;
//            b = count;
//            m--;
//        }
//    }
//    cout << count;
//}

////                                                      匹配串问题
//#include <cctype>
//#include <iostream>
//using namespace std;
//#include<string>
//#include<stdbool.h>
//bool match(const char* m, const char* str)
//{
//    if (*m == '\0' && *str == '\0')//结束判断
//        return true;
//    if (*m == '\0' || *str == '\0')//结束判断
//        return false;
//
//    if (*m == '?')
//    {
//        if (!isalpha(*str) && !isdigit(*str))//不为数字和字母时要跳过‘？’
//            return false;
//        return match(m+1, str+1);
//    }
//    else if (*m == '*')
//    {
//        while (*m == '*')//如果有多个连续的*所以去重
//        {
//            m++;
//        }
//        m--;
//        if (!isalpha(*str) && !isdigit(*str))//如果我们的str不为字母和数字则我们的*需要直接跳过
//            return match(m+1, str);
//        return match(m+1, str+1) || match(m, str+1) || match(m+1, str);//三种情况
//    }
//    else if (tolower(*m) == tolower(*str))//当不为字母也不为我们的数字时直接比较
//    {
//        return match(m+1, str+1);
//    }
//    return false;
//}
//int main() {
//    string str1, str2;
//    getline(cin, str1);
//    getline(cin, str2);
//    bool ret = match(str1.c_str(), str2.c_str());
//    if (ret == true)
//        cout << "true";
//    else
//        cout << "false";
//}

////                                                                 汽水瓶问题
//#include <iostream>
//using namespace std;
//int main() {
//    int n;
//    while (cin >> n) {
//        int count = 0;
//        while (n >= 3) {
//            count += n / 3;
//            n = n / 3 + n % 3;
//        }
//        if (n == 2)
//            count++;
//        if (count == 0)
//            exit(0);
//        cout << count << endl;
//    }
//    return 0;
//}

////                                                          字符串子串问题2023.10.27
//#include <iostream>
//#include<vector>
//#include<string>
//using namespace std;
//string match(string& str1, string& str2)
//{
//    if (str1.size() > str2.size())
//        swap(str1, str2);
//    int len1 = str1.size();
//    int len2 = str2.size();
//    vector<vector<int>>v(len1 + 1, vector<int>(len2 + 1, 0));
//    int max = 0, start = 0;
//    for (int i = 1; i <= len1; i++)
//    {
//        for (int j = 1; j <= len2; j++)
//        {
//            if (str1[i - 1] == str2[j - 1])
//                v[i][j] = v[i - 1][j - 1] + 1;
//            if (v[i][j] > max)
//            {
//                max = v[i][j];
//                start = i - max;
//            }
//        }
//    }
//    return str1.substr(start, max);
//}
//int main() {
//    string str1, str2;
//    getline(cin, str1);
//    getline(cin, str2);
//    int count = 0;
//    cout << match(str1, str2);
//}

//#include<iostream>//自己进行思考得出答案
//#include<string>
//#include<vector>
//using namespace std;
//string match(string& str1, string& str2)
//{
//    if (str1.size() > str2.size())//找出短的串
//        swap(str1, str2);
//    int row = str1.size();
//    int col = str2.size();
//    vector<vector<int>>v(row, vector<int>(col, 0));
//    int max = 0, start = 0;
//    for (int i = 0; i < row; i++)
//    {
//        for (int j = 0; j < col; j++)
//        {
//            if (str1[i] == str2[j])
//            {
//                if (i - 1 < 0 || j - 1 < 0)
//                    v[i][j]++;
//                else
//                    v[i][j] = v[i - 1][j - 1] + 1;
//                if (v[i][j] > max)
//                {
//                    max = v[i][j];
//                    start = i - max + 1;
//                }
//            }
//        }    
//    }
//    return str1.substr(start, max);
//}
//int main()
//{
//    string str1, str2;
//    getline(cin, str1);
//    getline(cin, str2);
//    cout<<match(str1, str2);
//    return 0;
//}

////测试地址空间，我们发现不论是函数还是普通变量他们在栈上都是向下增长的
//void test()
//{
//    int d;
//    int e;
//    printf("d:%p\ne:%p\n", &d, &e);
//    return;
//}
//int main()
//{
//    int a, b, c;
//    printf("a:%p\nb:%p\nc:%p\n", &a, &b, &c);
//    test();
//    return 0;
//}

////                                                          只出现一次的数2023.11.2
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        if (nums.size() == 0)
//            return 0;
//        int n = nums[0];
//        for (int i = 1; i < nums.size(); i++）
//        {
//            n ^= nums[i];
//        }
//        return n;
//    }
//};

////                                                               杨辉三角
//class Solution {
//public:
//    vector<vector<int>> generate(int numRows) {
//        vector<vector<int>>v;
//        for (int i = 0; i < numRows; i++)
//        {
//            vector<int>tmp;
//            for (int j = 0; j < i + 1; j++)
//            {
//                if (j == 0 || j == i)
//                {
//                    tmp.push_back(1);
//                }
//                else if (i > 1)
//                    tmp.push_back(v[i - 1][j - 1] + v[i - 1][j]);
//            }
//            v.push_back(tmp);
//        }
//        return v;
//    }
//};

////                                              删除vector中的重复数
//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int flag = 1;
//        for (int i = 1; i < nums.size(); i++)
//        {
//            if (nums[i] != nums[i - 1])
//                nums[flag++] = nums[i];
//        }
//        nums.resize(flag);
//        return flag;
//    }
//};

////                                                      数组中最大的子串数组大小2023.11.3
//int FindGreatestSumOfSubArray(vector<int>& array) {
//    int max = array[0];
//    for (int i = 1; i < array.size(); i++)
//    {
//        array[i] = array[i - 1] + array[i] > array[i] ? array[i - 1] + array[i] : array[i];
//        if (array[i] > max)
//            max = array[i];
//    }
//    return max;
//}
//};

////                                                          除一个数外的其他数都出现三次，找出这个只出现一次的数
//class Solution {
//public:
//    int singleNumber(vector<int>& nums) {
//        int num = 0;
//        for (int j = 0; j < 32; j++)
//        {
//            int sum = 0;
//            for (int i = 0; i < nums.size(); i++)
//            {
//               sum += (1 & (nums[i] >> j));
//            }
//            cout << sum << endl;
//            sum %= 3;
//            num |= (sum << j);
//        }
//        return num;
//    }
//};

////                                                          除去两个不同的数字之外每个数字都出现两次找出这两个不同的数字
//class Solution {
//public:
//    vector<int> singleNumber(vector<int>& nums) {
//        int sum = 0;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            sum ^= nums[i];
//        }
//        int flag = -1;
//        for (int i = 0; i < 32; i++)
//        {
//            if (((sum >> i) & 1) == 1)
//            {
//                flag = i;
//            }
//        }
//        vector<int> s(2, 0);
//        for (int i = 0; i < nums.size(); i++)
//        {
//            if (((nums[i] >> flag) & 1) == 1)
//                s[0] ^= nums[i];
//            else
//                s[1] ^= nums[i];
//        }
//        return s;
//    }
//};

////                                                             找出数组中出现次数超过数组元素个数一半的数
//int MoreThanHalfNum_Solution(vector<int>& numbers) {
//    int max = numbers[0];
//    int num = 1;
//    for (int i = 1; i < numbers.size(); i++)
//    {
//        if (num == 0)
//        {
//            max = numbers[i];
//            num = 1;
//        }
//        else {
//            if (numbers[i] != max)
//                num--;
//            else
//                num++;
//        }
//    }
//    return max;
//}
//};

////                                                         电话号码字母组合（自己实现）
//#include<string>
//#include<vector>
//class Solution {
//public:
//    string aph[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
//    void match(const char* digits, vector<string>& v, string str)
//    {
//        if (*digits == '\0')
//        {
//            v.push_back(str);
//            return;
//        }
//        int num = (*digits) - '0';
//        for (int i = 0; i < aph[num].size(); i++)
//        {
//            match(digits + 1, v, str+ aph[num][i]);
//        }
//    }
//    vector<string> letterCombinations(string digits) {
//        vector<string> v;
//        if (digits.size() == 0)
//            return v;
//        string str;
//        match(digits.c_str(), v, str);
//        return v;
//    }
//};
//int main()
//{
//    Solution a;
//    vector<string> v=a.letterCombinations("23");
//    for (int i = 0; i < v.size(); i++)
//    {
//        cout << v[i] <<" ";
//    }
//    return 0;
//}

////                                          最小栈题目2023.11.7
//class MinStack {
//public:
//    MinStack() {}
//    void push(int val) {
//        _s.push(val);
//        if (_min.empty() || val <= _min.top())
//            _min.push(val);
//    }
//    void pop() {
//        if (_s.top() == _min.top())
//        {
//            _min.pop();
//        }
//        _s.pop();
//    }
//    int top() {
//        return _s.top();
//    }
//    int getMin() {
//        return _min.top();
//    }
//private:
//    stack<int>_s;
//    stack<int>_min;
//};

////                                          判断栈的压入弹出序列是否正确
//class Solution {
//public:
//    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
//        stack<int>s;
//        int j = 0;
//        for (int i = 0; i < pushV.size(); i++)
//        {
//            s.push(pushV[i]);
//            while (!s.empty() && s.top() == popV[j])
//            {
//                s.pop();
//                j++;
//            }
//        }
//        return j == popV.size();
//    }
//};

////                                  逆波兰表达式求值（后缀表达式求值）
//class Solution {
//public:
//    int evalRPN(vector<string>& tokens) {
//        stack<int>num;
//        for (int i = 0; i < tokens.size(); i++)
//        {
//            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
//            {
//                int right = num.top();
//                num.pop();
//                int left = num.top();
//                num.pop();
//                switch (tokens[i].front())
//                {
//                case '+':
//                    num.push(left + right);
//                    break;
//                case '-':
//                    num.push(left - right);
//                    break;
//                case '*':
//                    num.push(left * right);
//                    break;
//                case '/':
//                    num.push(left / right);
//                    break;
//                }
//            }
//            else
//            {
//                num.push(stoi(tokens[i]));
//            }
//        }
//        return num.top();
//    }
//};

////                                          反转字符串2023.11.17
//#include <iostream>
//#include<string>
//using namespace std;
//void reverse(string& str)
//{
//    int left = 0, right = str.size() - 1;
//    while (left < right)
//    {
//        swap(str[left], str[right]);
//        left++;
//        right--;
//    }
//}
//int main() {
//    string str;
//    getline(cin, str);
//    reverse(str);
//    cout << str;
//}

////                                                      公共子串计算(最大)
//#include <iostream>
//#include<string>
//#include<vector>
//using namespace std;
//int getlength(string& max, string& min)
//{
//    vector<vector<int>> v(max.size(), vector<int>(min.size(), 0));
//    int count = 0;
//    for (int i = 0; i < max.size(); i++)
//    {
//        for (int j = 0; j < min.size(); j++)
//        {
//            if (max[i] == min[j])
//            {
//                if (i == 0 || j == 0)
//                {
//                    v[i][j] = 1;
//                }
//                else {
//                    v[i][j] = v[i - 1][j - 1] + 1;
//                }
//                if (v[i][j] > count)
//                    count = v[i][j];
//            }
//        }
//    }
//    return count;
//}
//int main() {
//    string s1, s2;
//    getline(cin, s1);
//    getline(cin, s2);
//    string max, min;
//    if (s1.size() > s2.size())
//    {
//        max = s1;
//        min = s2;
//    }
//    else
//    {
//        max = s2;
//        min = s1;
//    }
//    cout << getlength(max, min);
//}

////谈非类型模板参数的作用
//namespace my_array {
//    template<class T, size_t N>
//    class array
//    {
//    private:
//        T arr[N];
//    };
////如果没有这个非类型模板参数的话，我们就无法这样实现array类
////就像是这样
//    template<class T>
//    class array
//    {
//    private:
//        T arr[？];//我们的？怎么获得呢
//    };
//}
//int main()
//{
//    my_array::array<int, 10> a;
//    return 0;
//}

//	class Date
//	{
//	public:
//		Date(int year = 1, int month = 1, int day = 1)//构造函数
//		{
//			_year = year;
//			_month = month;
//			_day = day;
//		}
//		//~Date(); 
//		Date(const Date& d)//拷贝构造函数
//		{
//			_year = d._year;
//			_month = d._month;
//			_day = d._day;
//		}
//		bool operator >(const Date& d) const
//		{
//			return d._year < this->_year ||
//				d._year == this->_year && d._month < this->_month ||
//				d._year == this->_year && d._month == this->_month && d._day < this->_day;
//		}
//	private:
//		int _year;
//		int _month;
//		int _day;
//	};
//	//目前问题是你的，实例化的问题，你的T在特化的时候，const T&是一个的类型，这个是可以的
//	//template<class T>
//	//bool Greater(T  left,T right)
//	//{
//	//	return left > right;
//	//}
//	//template<>
//	//bool Greater<Date*>(Date* left, Date* right)
//	//{
//	//	return *left > *right;
//	//}
//
//	//这样子也是可以的，为什么呢？
//	//原因在于你对于特化理解存在误差
//	//1.特化的前提是有模板的情况下，这一点你是有的
//	//2.特化模板类型要和你特化的特性保持一致
//	template<class T>
//	bool Greater(T  left,T right)
//	{
//		return left > right;
//	}
//	template<>
//	bool Greater<Date *>(Date* left,Date* right)
//	{
//		return *left > *right; 
//	}
//int main()
//{
//	Date d(2023, 11, 19);
//	Date d1(2023, 11, 20);
//	cout<< Greater(&d, &d1);
//	return 0;
//}

////模板特化
//template <class T1, class T2>
//class A
//{
//public:
//	A()
//	{
//		cout << "A<T1,T2>" << endl;
//	}
//};
////类模板全特化
//template <>
//class A<int, char>
//{
//public:
//	A()
//	{
//		cout << "A<int ,char>" << endl;
//	}
//};
////类模板偏特化模板参数部分特化；
//template<class T2>
//class A<int,T2>
//{
//public:
//	A()
//	{
//		cout << "A<int,T2>" << endl;
//	}
//};
////对所有模板参数进一步处理：
//template<class T1,class T2>
//class A<T1*,T2*>
//{
//public:
//	A()
//	{
//		cout << "A<T1*,T2*>" << endl;
//	}
//};
//int main()
//{
//	A<int, int>a1;
//	A<int, char>a2;
//	A<int*, char*>a3;
//	return 0;
//}

//int main()
//{
//    int a = 5;
//    const int& b = a;//这里的引用并没有被常量替换，因为a不是常量；
//    printf("&a:%p  a=%d\n", &a,a);
//    printf("&b:%p  b=%d\n", &b,b);
//    a = 10;
//    printf("&a:%p  a=%d\n", &a, a);
//    printf("&b:%p  b=%d\n", &b, b);
//    return 0;
//}

//                              对继承的实验
//class person//父类
//{};
////子类
//class student :public person
//{};
//int main()
//{
//    student s;
//    person p = s;//父类可以直接接受子类
//    person* ptrs = &s;//指向子类的父类类型指针
//    person* ptrp = &p;//指向父类的父类类型指针
//
//    person& refs = s;//指向子类的父类类型引用
//    person& refp = p;//指向父类的父类类型引用
//
//    student* s1 = (student*)ptrp;//子类的指针或者引用可以接受强制类型的父类
//    student* s2 = (student*)ptrs;
//
//    student& s3 = (student&)refp;
//    student& s4 = (student&)refs;
//
//    return 0;
//}

////                                  实验拷贝构造是否会自动调用
//class A
//{
//protected:
//    int _a;
//    int _b;
//public:
//    A()
//    {
//        _a = 10;
//        _b = 20;
//    }
//    A(int a, int b)
//        :_a(a)
//        , _b(b)
//    {}
//    A(const A& copy)
//    {
//        _a = copy._a;
//        _b = copy._b;
//    }
//};
//class B:public A
//{
//public:
//    int _c;
//    B()
//    {
//        _c = 30;
//    }
//    B(int a, int b, int c)
//        :A(a,b)
//        ,_c(c)
//    {}
//    B(const B& copy)
//        :A(copy)
//    {
//        _c = copy._c;
//    }
//    void print()
//    {
//        cout << " a:" << _a << " b:" << _b << " c:" << _c << endl;
//    }
//};
//int main()
//{
//    B b1(1,1,1);
//    b1.print();
//    B b(b1);
//    b.print();
//    return 0;
//}

////                                      测试继承中构造和析构的顺序
//class A
//{
//public:
//    A()
//    {
//        cout << "我是A类的构造函数" << endl;
//    }
//    ~A()
//    {
//        cout << "我是A类的析构函数" << endl;
//    }
//};
//class B :public A
//{
//public:
//    B()
//    {
//        cout << "我是B类的构造函数" << endl;
//    }
//    ~B()
//    {
//        cout << "我是B类的析构函数" << endl;
//    }
//};
//int main()
//{
//    B b;
//    return 0;
//}

////                                      测试虚拟继承
//class A
//{
//protected:
//    int _a = 10;
//};
//class B :virtual public A
//{
//protected:
//    int _b = 20;
//};
//class C:virtual public A
//{
//protected:
//    int _c = 30;
//};
//class D:public B,public C
//{
//protected:
//    int _d = 40;
//};
//int main()
//{
//    D d;
//    return 0;
//}

////                                          组合的实践
//class A
//{
//public:
//    int _a=10;
//    int get_pa()
//    {
//        return _pa;
//    }
//protected:
//    int _pa=20;
//};
//class B
//{
//public:
//    int _b=30;
//    A _bA;
//    void print()
//    {
//        cout << _bA._a << endl;
//        cout << _bA.get_pa() << endl;
//    }
//};
//int main()
//{
//    B b;
//    b.print();
//    return 0;
//}

////                                                     移动零（将0移动到数组末尾，数组问题）
//class Solution {
//public:
//    void moveZeroes(vector<int>& nums) {
//        int nozero = -1, cur = 0;
//        while (cur != nums.size())
//        {
//            if (nums[cur] != 0)
//            {
//                swap(nums[++nozero], nums[cur]);
//            }
//            cur++;
//        }
//    }
//};
//int main()
//{
//    Solution s;
//    vector<int> v;
//    v.push_back(0);
//    v.push_back(1);
//    v.push_back(0);
//    v.push_back(0);
//    v.push_back(3);
//    v.push_back(12);
//    s.moveZeroes(v);
//    for (int i = 0; i < v.size(); i++)
//    {
//        cout <<v[i] << " ";
//    }
//    cout << endl;
//}

////              多态测试
//class A
//{
//public:
//    virtual void print(char ch ='a')
//    {
//        cout << "A->" << ch << endl;
//    }
//};
//class B :public A
//{
//public:
//    void print(char ch = 'b')
//    {
//        cout << "B->" << ch << endl;
//    }
//};
//int main()
//{
//    A* ptr = new(B);
//    ptr->print();
//    B b;
//    b.print();
//
//    return 0;
//}

////                          打印虚表并查看虚表中的操作2024.3.12
//class A
//{
//public:
//    virtual void fun()
//    {
//        cout << "A->fun()" << endl;
//    }
//    int _a = 1;
//};
//class B
//{
//public:
//    virtual void fun()
//    {
//        cout << "B->fun()" << endl;
//    }
//    int _b = 2;
//};
//class C:public A ,public B
//{
//public:
//    virtual void fun()
//    {
//        cout << "C->fun():";
//    }
//    virtual void fun1()
//    {
//        cout << "C->fun1():";
//    }
//    int _c = 3;
//};
//typedef void(*vfptr)();
//void printvtable(vfptr* vftable)
//{
//    for (int i = 0; vftable[i] != NULL; i++)
//    {
//        vftable[i]();
//        printf(" vftable[%d]->%p\n", i, vftable[i]);
//    }
//}
//int main()
//{
//    C c;
//    printvtable(*((vfptr**)&c));
//    B* ptr = &c;
//    printf("\n");
//    printvtable(*((vfptr**)ptr));
//    A* pa = &c;
//    B* pb = &c;
//    pa->fun();
//    pb->fun();
//    return 0;
//}

// //                                             多态
//class A
//{
//public:
//    virtual void fun()
//    {
//        cout << "A->fun():黑白打印" << endl;
//    }
//    int _a = 1;
//};
//class B :public A
//{
//public:
//    virtual void fun()
//    {
//        cout << "B->fun():彩印" << endl;
//    }
//    int _b = 2;
//};
//void print(A* ptr)//这就像一个打印机作为一个接口
//{
//    ptr->fun();
//}
//int main()
//{
//    A a;
//    B b;
//    print(&a);
//    print(&b);
//    return 0;
//}

//class A
//{
//public:
//    virtual void fun1()
//    {
//        cout << "C->fun1():";
//    }
//    virtual void fun2()
//    {
//        cout << "C->fun2():";
//    }
//    virtual void fun3()
//    {
//        cout << "C->fun3():";
//    }
//};
//class B:public A
//{
//public:
//    virtual void fun1()
//    {
//        cout << "C->fun1():";
//    }
//    virtual void fun2()
//    {
//        cout << "C->fun2():";
//    }
//    virtual void fun4()
//    {
//        cout << "C->fun4():";
//    }
//};
//typedef void(*vfptr)();
//
//void printvtable(vfptr* vftable)//打印虚函数表
//{
//    for (int i = 0; vftable[i] != NULL; i++)
//    {
//        vftable[i]();
//        printf(" vftable[%d]->%p\n", i, vftable[i]);
//    }
//}
//int main()
//{
//    A a;
//    B b;
//    printvtable(*(vfptr**)&a);
//    cout << "-------------------------" << endl;
//    printvtable(*(vfptr**)&b);
//    return 0;
//}

////                                        抽象类
//class A {
//public:
//    virtual void fun() = 0;
//};
//class B :public A {
//public:
//    virtual void fun()
//    {
//        cout << "B->fun()" << endl;
//    }
//};
//class C :public A {
//public:
//    virtual void fun()
//    {
//        cout << "C->fun()" << endl;
//    }
//};
//void print(A* ptr)
//{
//    ptr->fun();
//}
//int main()
//{
//    A a;
//    B b;
//    C c;
//    print(&b);
//    print(&c);
//    return 0;
//}

//class A {
//public:
//    void fun()
//    {
//        cout << "A->fun()" << endl;
//    }
//};
//class B:public A{
//public:
//    void fun()
//    {
//        cout << "B->fun()" << endl;
//    }
//};
//
//void print(A* ptr)
//{
//    ptr->fun();
//}
//int main()
//{
//    A a;
//    B b;
//    print(&a);
//    print(&b);
//
//    return 0;
//}

////                                              二叉树oj题目将二叉树创建成字符串2023.3.14
//class Solution {
//public:
//    string tree2str(TreeNode* root) {
//        if (root == nullptr)
//        {
//            return "";
//        }
//        string str = to_string(root->val);
//        if (root->left || root->right)
//        {
//            str.push_back('(');
//            str += tree2str(root->left);
//            str.push_back(')');
//        }
//        if (root->right)
//        {
//            str.push_back('(');
//            str += tree2str(root->right);
//            str.push_back(')');
//        }
//        return str;
//    }
//};

////                                                        二叉树层序遍历2023.3.14
//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> vv;
//        queue<TreeNode*> q;
//        int levelsize = 0;
//        if (root)
//        {
//            q.push(root);
//            levelsize = 1;
//        }
//        vector<int> level;//存储每层的数据
//        while (!q.empty())
//        {
//            TreeNode* pop = q.front();
//            q.pop();//出队列入我们的数组
//            level.push_back(pop->val);//将数据放入每层
//            levelsize--;
//            if (pop->left)//出了之后开始入队列
//                q.push(pop->left);
//            if (pop->right)
//                q.push(pop->right);
//            if (levelsize == 0)//一层出完了开始放入level中
//            {
//                levelsize = q.size();
//                vv.push_back(level);
//                level.clear();
//            }
//        }
//        return vv;
//    }
//};

//                                              双队列法解决层序遍历问题（上面问题的另一个解法）
//  struct TreeNode {
//      int val;
//      TreeNode *left;
//      TreeNode *right;
//      TreeNode() : val(0), left(nullptr), right(nullptr) {}
//      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
// 
//
//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//
//        vector<vector<int>> vv;
//        if (root == nullptr)
//            return vv;
//        queue<TreeNode*> qnode;
//        queue<int> qlevel;
//
//        qnode.push(root);
//        qlevel.push(0);
//
//        vv.push_back(vector<int>());//先插入一个空的vector<int>确保vv有空间
//        while (!qnode.empty())
//        {
//            TreeNode* pop = qnode.front();
//            int level = qlevel.front();
//
//            qnode.pop();// 节点出队列
//            qlevel.pop();// 节点层数出队列
//
//            if ((level + 1) > vv.size())
//                vv.push_back(vector<int>());
//
//            vv[level].push_back(pop->val);
//
//            if (pop->left)
//            {
//                qnode.push(pop->left);
//                qlevel.push(level + 1);
//            }
//            if (pop->right)
//            {
//                qnode.push(pop->right);
//                qlevel.push(level + 1);
//            }
//        }
//        return vv;
//    }
//
//};
//
//int main()
//{
//    Solution s;
//    TreeNode* t1 = new TreeNode(3);
//    TreeNode* t2 = new TreeNode(9);
//    TreeNode* t3 = new TreeNode(20);
//    TreeNode* t4 = new TreeNode(15);
//    TreeNode* t5 = new TreeNode(7);
//    t1->left = t2;
//    t1->right = t3;
//    t3->left = t4;
//    t3->right = t5;
//    vector<vector<int>> vv=s.levelOrder(t1);
//    for (int i=0; i < vv.size(); i++)
//    {
//        for (int j = 0; j < vv[i].size(); j++)
//        {
//            cout << vv[i][j] << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}

//                                                  层序遍历反转
//class Solution {
//public:
//    vector<vector<int>> levelOrderBottom(TreeNode* root) {
//        vector<vector<int>> vv;
//        queue<TreeNode*> q;
//        int levelsize = 0;
//        if (root)
//        {
//            q.push(root);
//            levelsize = 1;
//        }
//        vector<int> level;//存储每层的数据
//        while (!q.empty())
//        {
//            TreeNode* pop = q.front();
//            q.pop();//出队列入我们的数组
//            level.push_back(pop->val);//将数据放入每层
//            levelsize--;
//            if (pop->left)//出了之后开始入队列
//                q.push(pop->left);
//            if (pop->right)
//                q.push(pop->right);
//            if (levelsize == 0)//一层出完了开始放入level中
//            {
//                levelsize = q.size();
//                vv.push_back(level);
//                level.clear();
//            }
//        }
//        // vector<vector<int>> rev_vv;
//        // for(int i=vv.size()-1;i>=0;i--)
//        // {
//        //     rev_vv.push_back(vv[i]);
//        // }
//        reverse(vv.begin(), vv.end());
//        return vv;
//    }
//};

////                                                  查找树的公共节点（先序遍历查找）--利用我是我左右节点的根节点
//class Solution {
//public:
//    bool search(TreeNode* root, TreeNode* node)
//    {
//        if (root == nullptr)
//            return false;
//
//        return (root == node || search(root->left, node) || search(root->right, node));
//    }
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        //这样开头是先序遍历查找的
//        if (root == p || root == q)//先看根
//            return root;
//
//        bool pinleft = search(root->left, p);
//        bool pinright = !pinleft;
//
//        bool qinright = search(root->right, q);
//        bool qinleft = !qinright;
//
//        if ((pinleft && qinright) || (pinright && qinleft))
//            return root;
//        else if (pinleft && qinleft)
//            return lowestCommonAncestor(root->left, p, q);
//        else
//            return lowestCommonAncestor(root->right, p, q);
//    }
//};

////                                            上题的更优解法
//class Solution {
//public:
//    bool search(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode** parent)
//    {
//        if (root == nullptr)
//            return false;
//        bool nil = search(root->left, p, q, parent);
//        bool nir = search(root->right, p, q, parent);
//        if ((nil && nir) || ((root->val == q->val) && (nil || nir)) || ((root->val == p->val) && (nil || nir)))
//            *parent = root;
//        return ((root->val == q->val) || (root->val == p->val) || nil || nir);
//    }
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        //后续遍历查看（深度优先dfs）
//        TreeNode* parent = nullptr;
//        search(root, p, q, &parent);
//        return parent;
//    }

////                                                还是上面那个题--三叉链解法转换为链表相交
  //struct TreeNode {
  //    int val;
  //    TreeNode *left;
  //    TreeNode *right;
  //    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  //};
// 
//
//class Solution {
//public:
//    bool getlist(TreeNode* root, TreeNode* node, stack<TreeNode*>& s)
//    {
//        if (root == nullptr)
//            return false;
//        s.push(root);
//        if (root == node)
//            return true;
//        if (getlist(root->left, node, s))
//            return true;
//        if (getlist(root->right, node, s))
//            return true;
//        s.pop();
//        return false;
//    }
//    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//        //这是转换为三叉链方法
//        stack<TreeNode*> sp;
//        stack<TreeNode*> sq;
//        //创建两个栈来存放我们的路径，这样出栈就可以还原成链表相交问题了
//        getlist(root, p, sp);
//        getlist(root, q, sq);
//
//        while (sp.size() != sq.size())
//        {
//            sp.size() > sq.size() ? sp.pop() : sq.pop();
//        }
//        while (sp.top()!=sq.top())
//        {
//            sp.pop();
//            sq.pop();
//        }
//        return sp.top();
//    }
//};
//
//int main()
//{
//    TreeNode* t1 = new TreeNode(3);
//    TreeNode* t2 = new TreeNode(5);
//    TreeNode* t3 = new TreeNode(1);
//    TreeNode* t4 = new TreeNode(6);
//    TreeNode* t5 = new TreeNode(2);
//    TreeNode* t6 = new TreeNode(0);
//    TreeNode* t7 = new TreeNode(8);
//    TreeNode* t8 = new TreeNode(7);
//    TreeNode* t9 = new TreeNode(4);
//    t1->left = t2;
//    t1->right = t3;
//    t2->left = t4;
//    t2->right = t5;
//    t3->left = t6;
//    t3->right = t7;
//    t5->left = t8;
//    t5->right = t9;
//    Solution s;
//    cout<<s.lowestCommonAncestor(t1, t2, t3)->val;
//
//    return 0;
//}

////                                      将树转换为中序双向链表（二叉搜索树与双向链表）2024.3.15
//class Solution {
//public:
//	void connect(TreeNode* cur, TreeNode*& prev)//中序遍历
//	{
//		if (cur == nullptr)
//			return;
//		connect(cur->left, prev);//调用操作左节点
//		cur->left = prev;//更改当前节点的左指针
//		if (prev)//改变上一节点prev的右节点
//			prev->right = cur;
//		prev = cur;//操作完成之后，当前节点也是返回到上一节点的prev（因为我们也是被调用的节点之一）
//		connect(cur->right, prev);//调用操作右节点
//	}
//	TreeNode* Convert(TreeNode* pRootOfTree) {
//		TreeNode* prev = nullptr;
//		connect(pRootOfTree, prev);//调用函数进行中序遍历
//		TreeNode* head = pRootOfTree;
//		while (head && head->left)//使得指针指向最左节点（也是链表的起始节点）
//		{
//			head = head->left;
//		}
//		return head;
//	}
//};

//                                            通过前序和中序获得树形状--从前序与中序遍历序列构造二叉树
//struct TreeNode {
//    int val;
//    TreeNode* left;
//    TreeNode* right;
//    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
//};
//void print(TreeNode* root)
//{
//    if (root == nullptr)
//    {
//        cout << "null" << " ";
//        return;
//    }
//    cout << root->val << " ";
//    print(root->left);
//    print(root->right);
//}
//
//class Solution {
//public:
//    TreeNode* create(vector<int>& preorder, vector<int>& inorder, int& proot, int begin, int end)
//    {
//        if (proot > preorder.size() - 1 || begin > end)//当前序遍历完了，或者是自己的左右区间再无法划分了
//            return nullptr;
//        int rooti = begin;
//        TreeNode* root = new TreeNode(preorder[proot]);
//        proot++;
//        while (rooti <= end)//在中序中寻找子节点
//        {
//            if (inorder[rooti] == root->val)
//            {
//                break;
//            }
//            rooti++;
//        }
//        //划分区间[begin,rooti-1]rooti[rooti+1,end]
//        root->left = create(preorder, inorder, proot, begin, rooti - 1);
//        root->right = create(preorder, inorder, proot, rooti + 1, end);
//        return root;
//    }
//
//    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//        int tmp = 0;
//        return create(preorder, inorder, tmp, 0, preorder.size() - 1);
//    }
//};
//
//int main()
//{
//    vector<int> v = { 3,9,20,15,7 };
//    vector<int>v1 = { 9,3,15,20,7 };
//    Solution s;
//    print(s.buildTree(v, v1));
//
//    return 0;
//}

////                                                  从中序与后序遍历序列构造二叉树
//class Solution {
//public:
//    TreeNode* create(vector<int>& preorder, vector<int>& inorder, int& proot, int begin, int end)
//    {
//        if (proot<0 || begin>end)
//            return nullptr;
//        int rooti = begin;
//        TreeNode* root = new TreeNode(preorder[proot]);
//        proot--;
//        while (rooti <= end)
//        {
//            if (inorder[rooti] == root->val)
//            {
//                break;
//            }
//            rooti++;
//        }
//        //划分区间[begin,rooti-1]rooti[rooti+1,end]
//        root->right = create(preorder, inorder, proot, rooti + 1, end);
//        root->left = create(preorder, inorder, proot, begin, rooti - 1);
//        return root;
//    }
//    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//        int tmp = postorder.size() - 1;
//        return create(postorder, inorder, tmp, 0, postorder.size() - 1);
//    }
//};

////                                  二叉树的前序遍历（非递归）
//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        stack<TreeNode*> s;
//        vector<int>v;
//        TreeNode* cur = root;
//        while (cur || !s.empty())
//        {
//            while (cur)
//            {
//                s.push(cur);
//                v.push_back(cur->val);
//                cur = cur->left;
//            }
//
//            TreeNode* top = s.top();
//            s.pop();
//            cur = top->right;
//        }
//        return v;
//    }
//};

////                            二叉树中序遍历(非递归)
//class Solution {
//public:
//    vector<int> inorderTraversal(TreeNode* root) {
//        stack<TreeNode*> s;
//        vector<int> v;
//        TreeNode* cur = root;
//        while (cur || !s.empty())
//        {
//            while (cur)
//            {
//                s.push(cur);
//                cur = cur->left;
//            }
//            TreeNode* top = s.top();
//            s.pop();
//            v.push_back(top->val);
//            cur = top->right;
//
//        }
//        return v;
//    }
//};


////                            二叉树后序遍历（非递归）
//class Solution {
//public:
//    vector<int> postorderTraversal(TreeNode* root) {
//        stack<TreeNode*> s;
//        vector<int> v;
//        TreeNode* cur = root;
//        TreeNode* prev = nullptr;
//        while (cur || !s.empty())
//        {
//            while (cur)
//            {
//                s.push(cur);
//                cur = cur->left;
//            }
//            TreeNode* top = s.top();
//            if (top->right == nullptr || top->right == prev)
//            {
//                v.push_back(top->val);
//                s.pop();
//                prev = top;//记录一下上次弹出栈的元素，防止再次进入栈中
//            }
//            else
//            {
//                cur = top->right;
//            }
//        }
//        return v;
//    }
//};

//                                          set和multiset测试
//int main()
//{
//    /*int arr[] = { 8,6,2,4,5,3,1,7,9 };
//    set<int> s_range(arr, arr + 9);
//    cout << "s_range: ";
//    for (auto x : s_range)
//    {
//        cout << x << " ";
//    }
//    cout << endl;
//    set<int> s_empty;
//    s_empty.insert(5);
//    s_empty.insert(8);
//    s_empty.insert(4);
//    s_empty.insert(9);
//    s_empty.insert(7);
//    s_empty.insert(3);
//    set<int>::iterator ret = s_empty.begin();
//    cout <<"s_empty: ";
//    while (ret != s_empty.end())
//    {
//        cout << *ret << " ";
//        ret++;
//    }
//    cout << endl;
//    set<int> s_copy(s_empty);
//    cout << "s_copy: ";
//    for (auto x : s_copy)
//    {
//        cout << x << " ";
//    }
//    cout << endl;*/
//    int arr[] = { 5,3,7,2,4,6,6,6,8 };
//    multiset<int> s;
//    for (auto x : arr)
//    {
//        s.insert(x);
//    }
//    cout << "全部元素：";
//    for (auto x : s)
//    {
//        cout  << x << " ";
//    }
//    cout << endl;
//    auto ret=s.find(6);
//    cout << "find的第一个元素开始：";
//    while (ret != s.end())
//    {
//        cout << *ret << " ";
//        ret++;
//    }
//    cout << endl;
//}

//              map中的[]运算符重载解释
//V& operator[](const K& key)
//{
//    pair ret=map.insert(make_pair(key, V()));
//    return ret.first.second;
//}

//int main()
//{
//    map<int, string>m;
//    m.insert(make_pair(3, "wangwu"));
//    m.insert(make_pair(4, "zhaoliu"));
//    m.insert(make_pair(1, "zhangsan"));
//    m.insert(make_pair(2,"lisi"));
//    for (auto x : m)
//    {
//        cout << x.first << ":" << x.second << endl;
//    }
//    cout << "----------------------------"<<endl;
//    m[5];//插入操作，我们没有修改任何数据，但是map中没有这个元素5所以会直接插入
//    for (auto x : m)
//    {
//        cout << x.first << ":" << x.second << endl;
//    }
//    cout << "----------------------------"<<endl;
//    m[5] = "chengqi";//修改value操作
//    for (auto x : m)
//    {
//        cout << x.first << ":" << x.second << endl;
//    }
//    cout << "----------------------------" << endl;
//
//    return 0;
//}

////                                              2024.4.14随机链表的复制
////c++
//class Solution {
//public:
//    Node* copyRandomList(Node* head) {
//        if (head == NULL)
//            return NULL;
//        Node* newhead, * newtail;
//        newhead = NULL;
//        newtail = NULL;
//        Node* cur = head;
//        map<Node*, Node*>m;
//        while (cur)
//        {
//            Node* newnode = new Node(cur->val);
//            m.insert(make_pair(cur, newnode));//存放好当前节点的random和新建节点的映射关系
//            if (newhead == NULL)
//            {
//                newhead = newtail = newnode;
//            }
//            else
//            {
//                newtail->next = newnode;
//                newtail = newnode;
//            }
//            cur = cur->next;
//        }
//        Node* copy = newhead;
//        cur = head;
//        while (cur)
//        {
//            copy->random = m[cur->random];
//            cur = cur->next;
//            copy = copy->next;
//        }
//
//        return newhead;
//    }
//};

////                                  2024.4.15前K个高频单词(力扣)
//class Solution {
//public:
//    template<class K>
//    struct compare
//    {
//        bool operator()(const K& k1, const K& k2)const
//        {
//            return k1.second > k2.second || k1.second == k2.second && k1.first < k2.first;
//        }
//    };
//
//    vector<string> topKFrequent(vector<string>& words, int k) {
//        map<string, int>m;
//        for (auto str : words)
//        {
//            m[str]++;
//        }
//        //debug
//        // for(auto it:m)
//        // {
//        //     cout<<it.first<<":"<<it.second<<" ";
//        // }
//        // cout<<endl;
//        set<pair<string, int>, compare<pair<string, int>>>s;
//        for (auto it : m)
//        {
//            s.insert(it);
//        }
//        vector<string> v;
//        int i = 0;
//        for (auto it : s)
//        {
//            v.push_back(it.first);
//            if (++i == k)
//            {
//                break;
//            }
//        }
//        return v;
//    }
//
//};

//											2024.4.15两个数组的交集
//class Solution {
//public:
//    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//        // 排序加去重
//        set<int> s1(nums1.begin(), nums1.end());
//        set<int> s2(nums2.begin(), nums2.end());
//
//        auto cur1 = s1.begin();
//        auto cur2 = s2.begin();
//
//        vector<int> v;
//        while (cur1 != s1.end() && cur2 != s2.end())
//        {
//            if (*cur1 == *cur2)
//            {
//                v.push_back(*cur1);
//                cur1++;
//                cur2++;
//            }
//            else if (*cur1 < *cur2) {
//                cur1++;
//            }
//            else {
//                cur2++;
//            }
//        }
//        return v;
//    }
//};
//void test()
//{
//    Solution s;
//    vector<int> v1 = { 4,9,5 };
//    vector<int> v2 = { 9,4,9,8,4 };
//    
//    for (auto it : s.intersection(v1, v2))
//    {
//        cout << it << " ";
//    }
//}
//
//int main()
//{
//    test();
//    return 0;
//}

//										温故一下
//void test()
//{
//	vector<int>arr;
//	srand(time(nullptr));
//	int n = 100;
//	for (int i = 0; i < n; i++)
//	{
//		arr.push_back(rand()%100);
//	}
//
//	for (int i = 0; i < n-1; i++)
//	{
//		for (int j = 0; j < n-i-1; j++)
//		{
//			if (arr[j] < arr[j + 1])
//			{
//				swap(arr[j], arr[j + 1]);
//			}
//		}
//	}
//	for (auto it : arr)
//	{
//		cout << it << " ";
//	}
//	cout << endl;
//}
//int main()
//{
//	test();
//	return 0;
//}

//								test
//int main()
//{
//
//	int a = 32;
//	int b = 128;
//	cout << MAXSIZE_T << endl;
//	//cout << MAXUNSIGNED_INT << endl;
//	return 0;
//
//}

//////										测试C++11{}符号初始化
////
//void test()
//{
//	int a = 0;
//	int b{ 1 };
//	int c = { 1 };
//	cout << "test()" << endl;
//	cout << &a << endl;
//	cout << &b << endl;
//	cout << &c << endl;
//}
//void test1()
//{
//	int a = 10;
//	int b = { 10 };
//	int c{ 10 };
//	vector<int> v{ 1,2,3,4,5 };
//	int* pa = { &a };
//	int arr[]{ 1,2,3,4 };
//	cout << &a << endl;
//	cout << &b << endl;
//	cout << &c << endl;
//	test();
//}
//
//class A {
//public:
//	A(string str)//单参数构造参数可以自动进行类型转化
//		:_a(str)
//	{
//		cout << "A() 构造函数" << endl;
//	}
//private:
//	string _a;
//};
//int main()
//{
//	A a{ "123" };
//	return 0;
//}

////														decltype关键字								
//int main()
//{
//	int a = 10;
//	double b = 25.0;
//	vector<decltype(b / a)> v;
//	cout << typeid(v).name() << endl;
//	return 0;
//}

////												右值引用
//void test()
//{
//	string a = "hello";
//	string b = " world!";
//	//左值引用
//	string& refa = a;
//	const string& refab = a + b;//可以使用const来接收右值（因为临时对象具有常性）
//
//	//右值引用
//	string&& rrefb = move(b);//可以使用move函数将左值转换为右值来接收接收
//	string&& rrefab = a + b;
//
//	list<int> l{ 1,2,3,4,5,6 };
//	list<int> l1 = move(l);//拷贝构造时右值的数据会被转移走
//}


////								我发现编译器对于拷贝构造进行了很多的优化，有时候并不会调用拷贝构造
//struct A
//{
//	string _str;
//	A(const string& str)
//		:_str(str)
//	{
//		cout << "构造函数A(const string& str)" << endl;
//	}
//	A()
//		:_str("")
//	{
//		cout << "构造函数A()" << endl;
//	}
//	A(const A& a)
//		:_str(a._str)
//	{
//		cout << "深拷贝A(const A& a)" << endl;
//	}
//	A(A&& a)
//	{
//		swap(_str, a._str);
//		cout << "移动构造A(A&& a)" << endl;
//		(void)a;
//	}
//	~A()
//	{}
//};
//
//int main()
//{
//	string s("hello");
//	A a(s);//普通构造函数
//	A c(a);//深拷贝
////A b(A());//这样会被编译器翻译为一个函数的声明，声明了一个叫b的函数，返回值类型为A，参数为返回值为A的无参函数
////A b(A{});//本来要调用移动构造的但是，由于编译器优化,直接进行了一次构造
//	A b(move(a));//移动构造
// 
//
//	return 0;
//}

////												完美转发
//
//void func(const string& a)
//{
//	cout << "左值" << endl;
//}
//
//void func(string && a)
//{
//	cout<<"右值" << endl;
//}
//
//template<class T>
//void test1(T&&a)
//{
//	//func(a);//a引用接收右值之后，他自己便成为了左值
//
//	func(forward<T>(a));//完美转发，保持a右值的状态
//}
//
//void test()
//{
//	string a;
//	test1(a);
//	test1(move(a));
//}
//
//int main()
//{
//	test();
//	return 0;
//}

////									测试临时对象返回
//struct A
//{
//	int _a ;
//	int _b ;
//	A(const A& a)
//	{
//		_a = a._a;
//		_b = a._b;
//		//noting
//	}
//
//	A(int a,int b)
//		:_a(a)
//		,_b(b)
//	{	
//	}
//};
//A& getA()
////A getA()
//{
//	A a(10, 20);
//	return a;
//}
//int main()
//{
//	const A& b = getA();
//	string("11111111111");
//}
